refs/reftable: wire up exclude patterns
cover refs/reftable: wire up exclude patterns
Hi,
this patch series wires up exclude patterns for the reftable backend. Exclude patterns allow the backend to skip references internally that match a specific pattern. This avoids having to read references that the caller would discard immediately anyway.
The series is structured as follows:
- Patches 1 and 2 fix two separate bugs in how we currently handle exclude patterns in combination with namespaces. We didn't happen to stumble over these bugs before because exclude patterns are only implemented for the "packed" backend. But once you start to pack refs we exclude references based on their full name instead of the name with the prefixed stripped. For the reftable backend we'd always hit those bugs because it always uses exclude patterns when passed.
- Patches 3 to 5 wire up proper re-seeking of reftable iterators and adds some tests to demonstrate that this works as expected. This is a prerequisite for handling exclude patterns.
- Patch 6 wires up exclude patterns in the reftable backend by re-seeking iterators once we hit an excluded reference.
Thanks!
Patrick
Patrick Steinhardt (6):
refs: properly apply exclude patterns to namespaced refs builtin/receive-pack: fix exclude patterns when announcing refs
Makefile: stop listing test library objects twice t/unit-tests: introduce reftable library reftable/reader: make table iterator reseekable refs/reftable: wire up support for exclude patterns
Makefile | 8 +- builtin/receive-pack.c | 18 ++- refs.c | 35 +++++- refs.h | 9 ++ refs/reftable-backend.c | 125 ++++++++++++++++++++- reftable/reader.c | 1 + t/t1419-exclude-refs.sh | 33 ++++-- t/t5509-fetch-push-namespaces.sh | 9 ++ t/unit-tests/lib-reftable.c | 93 ++++++++++++++++ t/unit-tests/lib-reftable.h | 20 ++++ t/unit-tests/t-reftable-merged.c | 163 +++++++++++++++------------- t/unit-tests/t-reftable-reader.c | 96 ++++++++++++++++ t/unit-tests/t-reftable-readwrite.c | 130 +++++++--------------- t/unit-tests/t-reftable-stack.c | 25 ++--- trace2.h | 1 + trace2/tr2_ctr.c | 5 + 16 files changed, 570 insertions(+), 201 deletions(-) create mode 100644 t/unit-tests/lib-reftable.c create mode 100644 t/unit-tests/lib-reftable.h create mode 100644 t/unit-tests/t-reftable-reader.c
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
PATCH 1/6 refs: properly apply exclude patterns to namespaced refs
Reference namespaces allow commands like git-upload-pack(1) to serve different sets of references to the client depending on which namespace is enabled, which is for example useful in fork networks. Namespaced refs are stored with a refs/namespaces/$namespace prefix, but all the user will ultimately see is a stripped version where that prefix is removed.
The way that this interacts with "transfer.hideRefs" is not immediately
obvious: the hidden refs can either apply to the stripped references, or to the non-stripped ones that still have the namespace prefix. In fact, the "transfer.hideRefs" machinery does the former and applies to the stripped reference by default, but rules can have "^" prefixed to switch this behaviour to iinstead match against the rull reference name.
Namespaces are exclusively handled at the generic "refs" layer, the respective backends have no clue that such a thing even exists. This also has the consequence that they cannot handle hiding references as soon as reference namespaces come into play because they neither know whether a namespace is active, nor do they know how to strip references if they are active.
Handling such exclude patterns in refs_for_each_namespaced_ref() and refs_for_each_fullref_in_prefixes() is broken though, as both support that the user passes both namespaces and exclude patterns. In the case where both are set we will exclude references with unstripped names, even though we really wanted to exclude references based on their stripped names.
This only surfaces when:
- A repository uses reference namespaces.
- "transfer.hideRefs" is active.
- The namespaced references are packed into the "packed-refs" file.
None of our tests exercise this scenario, and thus we haven't ever hit it. While t5509 exercises both (1) and (2), it does not happen to hit (3). It is trivial to demonstrate the bug though by explicitly packing refs in the tests, and then we indeed surface the breakage.
Fix this bug by prefixing exclude patterns with the namespace in the generic layer.
--- refs.c | 35 ++++++++++++++++++++++++++++---- refs.h | 9 ++++++++ t/t5509-fetch-push-namespaces.sh | 1 + 3 files changed, 41 insertions(+), 4 deletions(-)
refs.c +31 -4
@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out) +{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns) +return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +const char *find_descendant_ref (const char *dirname,const struct string_list *extras,const struct string_list *skip)
@@ -1634,11 +1647,19 @@ int refs_for_each_namespaced_ref(struct ref_store *refs,const char **exclude_patterns, each_ref_fn fn, void *cb_data) { - struct strbuf buf = STRBUF_INIT; + struct strvec namespaced_exclude_patterns = STRVEC_INIT; +struct strbuf prefix =STRBUF_INIT ;int ret; -strbuf_addf (&buf,"%srefs/" ,get_git_namespace ()); - ret =do_for_each_ref (refs, buf.buf, exclude_patterns, fn,0 ,0 , cb_data); -strbuf_release (&buf); + + exclude_patterns =get_namespaced_exclude_patterns (exclude_patterns, +get_git_namespace (), + &namespaced_exclude_patterns); + +strbuf_addf (&prefix,"%srefs/" ,get_git_namespace ()); + ret =do_for_each_ref (refs, prefix.buf, exclude_patterns, fn,0 ,0 , cb_data); + +strvec_clear (&namespaced_exclude_patterns); +strbuf_release (&prefix);return ret; }
@@ -1719,6 +1740,7 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,const char **exclude_patterns, each_ref_fn fn, void *cb_data) { + struct strvec namespaced_exclude_patterns = STRVEC_INIT;struct string_list prefixes =STRING_LIST_INIT_DUP ;struct string_list_item *prefix;struct strbuf buf =STRBUF_INIT ;
@@ -1730,6 +1752,10 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,strbuf_addstr (&buf, namespace); namespace_len = buf.len; + exclude_patterns =get_namespaced_exclude_patterns (exclude_patterns, + namespace, + &namespaced_exclude_patterns); +for_each_string_list_item (prefix, &prefixes) {strbuf_addstr (&buf, prefix->string); ret = refs_for_each_fullref_in(ref_store, buf.buf,
@@ -1739,6 +1765,7 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,strbuf_setlen (&buf, namespace_len); } +strvec_clear (&namespaced_exclude_patterns);string_list_clear (&prefixes,0 );strbuf_release (&buf);return ret;
refs.h +9 -0
@@ -859,6 +859,15 @@ int ref_is_hidden(const char *, const char *, const struct strvec *);*/ const char **hidden_refs_to_excludes (const struct strvec *hide_refs); +/* +* Prefix all exclude patterns with the namespace, if any. This is required +* because exclude patterns apply to the stripped reference name, not the full +* reference name with the namespace. +*/ +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out); +/* Is this a per-worktree ref living in the refs/ namespace? */ int is_per_worktree_ref (const char *refname);
t/t5509-fetch-push-namespaces.sh +1 -0
@@ -96,6 +96,7 @@ test_expect_success 'hide namespaced refs with transfer.hideRefs' ' ' test_expect_success 'check that transfer.hideRefs does not match unstripped refs' ' + git -C pushee pack-refs --all && GIT_NAMESPACE=namespace \ git -C pushee -c transfer.hideRefs=refs/namespaces/namespace/refs/tags \ ls-remote "ext::git %s ." >actual &&
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
Re: [PATCH 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 7 lines · Patrick Steinhardt
Reference namespaces allow commands like git-upload-pack(1) to serve different sets of references to the client depending on which namespace is enabled, which is for example useful in fork networks. Namespaced refs are stored with a
refs/namespaces/$namespaceprefix, but all the user will ultimately see is a stripped version where that prefix is removed.
Quoted 6 lines
The way that this interacts with "transfer.hideRefs" is not immediately
obvious: the hidden refs can either apply to the stripped references, or to the non-stripped ones that still have the namespace prefix. In fact, the "transfer.hideRefs" machinery does the former and applies to the stripped reference by default, but rules can have "^" prefixed to switch this behaviour to iinstead match against the rull reference name.
s/iinstead/instead
s/rull/full
Quoted 14 lines
Namespaces are exclusively handled at the generic "refs" layer, the respective backends have no clue that such a thing even exists. This also has the consequence that they cannot handle hiding references as soon as reference namespaces come into play because they neither know whether a namespace is active, nor do they know how to strip references if they are active.
Handling such exclude patterns in
refs_for_each_namespaced_ref()andrefs_for_each_fullref_in_prefixes()is broken though, as both support that the user passes both namespaces and exclude patterns. In the case where both are set we will exclude references with unstripped names, even though we really wanted to exclude references based on their stripped names.
Quoted 8 lines
This only surfaces when:
- A repository uses reference namespaces.
- "transfer.hideRefs" is active.
- The namespaced references are packed into the "packed-refs" file.
So this is because we don't even apply exclude patterns to the loose refs right?
To understand correctly, the transport layer passes on 'transfer.hideRefs' as exclude_refs to the generic refs layer. This is mostly to optimize the reference backend to skip such refs. This is used by the packed-refs currently but not used for loose refs.
The transfer layer also uses this list in mark_our_ref() to skip refs as needed.
So all in all exclude_refs here is mostly for optimization.
Quoted 4 lines
None of our tests exercise this scenario, and thus we haven't ever hit it. While t5509 exercises both (1) and (2), it does not happen to hit (3). It is trivial to demonstrate the bug though by explicitly packing refs in the tests, and then we indeed surface the breakage.
Nit: I know you're referring to the three points stated above, it would be nice if they were numbered.
Quoted 15 lines
Fix this bug by prefixing exclude patterns with the namespace in the generic layer.
Signed-off-by Patrick Steinhardt <[email protected]>--- refs.c | 35 ++++++++++++++++++++++++++++---- refs.h | 9 ++++++++ t/t5509-fetch-push-namespaces.sh | 1 + 3 files changed, 41 insertions(+), 4 deletions(-)refs.c +0
-0
refs.c const char **hidden_refs_to_excludes(const struct strvec *hide_refs) · line 1524
Quoted 8 lines
refs.c +5
-0@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out) +{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns)
What scenario would !*namespace be possible?
Quoted 69 lines
refs.c +26
-4+return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +const char *find_descendant_ref (const char *dirname,const struct string_list *extras,const struct string_list *skip)@@ -1634,11 +1647,19 @@ int refs_for_each_namespaced_ref(struct ref_store *refs,const char **exclude_patterns, each_ref_fn fn, void *cb_data) { - struct strbuf buf = STRBUF_INIT; + struct strvec namespaced_exclude_patterns = STRVEC_INIT; +struct strbuf prefix =STRBUF_INIT ;int ret; -strbuf_addf (&buf,"%srefs/" ,get_git_namespace ()); - ret =do_for_each_ref (refs, buf.buf, exclude_patterns, fn,0 ,0 , cb_data); -strbuf_release (&buf); + + exclude_patterns =get_namespaced_exclude_patterns (exclude_patterns, +get_git_namespace (), + &namespaced_exclude_patterns); + +strbuf_addf (&prefix,"%srefs/" ,get_git_namespace ()); + ret =do_for_each_ref (refs, prefix.buf, exclude_patterns, fn,0 ,0 , cb_data); + +strvec_clear (&namespaced_exclude_patterns); +strbuf_release (&prefix);return ret; }@@ -1719,6 +1740,7 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,const char **exclude_patterns, each_ref_fn fn, void *cb_data) { + struct strvec namespaced_exclude_patterns = STRVEC_INIT;struct string_list prefixes =STRING_LIST_INIT_DUP ;struct string_list_item *prefix;struct strbuf buf =STRBUF_INIT ;@@ -1730,6 +1752,10 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,strbuf_addstr (&buf, namespace); namespace_len = buf.len; + exclude_patterns =get_namespaced_exclude_patterns (exclude_patterns, + namespace, + &namespaced_exclude_patterns); +for_each_string_list_item (prefix, &prefixes) {strbuf_addstr (&buf, prefix->string); ret = refs_for_each_fullref_in(ref_store, buf.buf,@@ -1739,6 +1765,7 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,strbuf_setlen (&buf, namespace_len); } +strvec_clear (&namespaced_exclude_patterns);string_list_clear (&prefixes,0 );strbuf_release (&buf);return ret;refs.h +0
-0@@ -859,6 +859,15 @@ int ref_is_hidden(const char *, const char *, const struct strvec *);*/ const char **hidden_refs_to_excludes (const struct strvec *hide_refs);
refs.h int ref_is_hidden(const char *, const char *, const struct strvec *); · line 870
Quoted 10 lines
refs.h +9
-0+/* +* Prefix all exclude patterns with the namespace, if any. This is required +* because exclude patterns apply to the stripped reference name, not the full +* reference name with the namespace. +*/ +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out); +
Do we need to expose this? Can't it be made static?
Re: [PATCH 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 25 lines · karthik nayak
Quoted 7 lines · Patrick Steinhardt
Handling such exclude patterns in
refs_for_each_namespaced_ref()andrefs_for_each_fullref_in_prefixes()is broken though, as both support that the user passes both namespaces and exclude patterns. In the case where both are set we will exclude references with unstripped names, even though we really wanted to exclude references based on their stripped names.Quoted 8 lines
This only surfaces when:
- A repository uses reference namespaces.
- "transfer.hideRefs" is active.
- The namespaced references are packed into the "packed-refs" file.
So this is because we don't even apply exclude patterns to the loose refs right?
To understand correctly, the transport layer passes on 'transfer.hideRefs' as
exclude_refsto the generic refs layer. This is mostly to optimize the reference backend to skip such refs. This is used by the packed-refs currently but not used for loose refs.
Quoted 4 lines
The transfer layer also uses this list in
mark_our_ref()to skip refs as needed.So all in all
exclude_refshere is mostly for optimization.
Yup.
Quoted 8 lines
Quoted 8 lines
refs.c +0
-0@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; }
Quoted 7 lines
refs.c const char **hidden_refs_to_excludes(const struct strvec *hide_refs) · line 1524
Quoted 5 lines
refs.c +5
-0+const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out) +{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns)What scenario would
!*namespacebe possible?
It's the default value of get_git_namespace().
Quoted 8 lines
Quoted 8 lines
refs.h +0
-0@@ -859,6 +859,15 @@ int ref_is_hidden(const char *, const char *, const struct strvec *);*/ const char **hidden_refs_to_excludes (const struct strvec *hide_refs);
Quoted 11 lines
refs.h int ref_is_hidden(const char *, const char *, const struct strvec *); · line 870
Quoted 9 lines
refs.h +9
-0+/* +* Prefix all exclude patterns with the namespace, if any. This is required +* because exclude patterns apply to the stripped reference name, not the full +* reference name with the namespace. +*/ +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out); +Do we need to expose this? Can't it be made static?
It will be used by the next patch. I'll amen the commit message to point this out.
Patrick
PATCH 2/6 builtin/receive-pack: fix exclude patterns when announcing refs
In reply to Patrick SteinhardtIn write_head_info() we announce references to the remote client. We need to honor "transfer.hideRefs" here so that we do not announce any references that the client shouldn't be able to learn about. This is done via two separate mechanisms:
- We hand over exclude patterns to the reference backend. We can only honor "plain" exclude patterns here that do not have prefixes with special meaning such as "^" or "!". Filtering down the references is handled by hidden_refs_to_excludes().
- In show_ref_cb() we perform a second check against hidden refs. For one this is done such that we can handle those special prefixes. And second, handling exclude patterns in ref backends is optional, so we also have to handle "normal" patterns.
The special-meaning "^" prefix alters whether a hidden ref applies to the namespace-stripped reference name or the full name. So while we would usually call refs_for_each_namespaced_ref() to only get those references in the current namespace, we can't because we'd get the already-rewritten reference names. Instead, we are forced to use refs_for_each_fullref_in() and then manually strip away the namespace prefix such that we have access to both names.
But this also means that we do not get namespace handling for exclude patterns, which refs_for_each_namespaced_ref() brings for free. This results in a bug because we potentially end up hiding away references based on their namespaced name and not on the stripped name as we really should be doing.
Fix this by manually rewriting the exclude patterns to their namespaced variants.
--- builtin/receive-pack.c | 18 ++++++++++++++++-- t/t5509-fetch-push-namespaces.sh | 8 ++++++++ 2 files changed, 24 insertions(+), 2 deletions(-)
builtin/receive-pack.c +16 -2
@@ -339,12 +339,26 @@ static void show_one_alternate_ref(const struct object_id *oid,static void write_head_info (void ) {static struct oidset seen =OIDSET_INIT ; +struct strvec excludes_vector =STRVEC_INIT ; +const char **exclude_patterns; + +/* +* We need access to the reference names both with and without their +* namespace and thus cannot use `refs_for_each_namespaced_ref()`. We +* thus have to adapt exclude patterns to carry the namespace prefix +* ourselves. +*/ + exclude_patterns =get_namespaced_exclude_patterns ( +hidden_refs_to_excludes (&hidden_refs), +get_git_namespace (), &excludes_vector);refs_for_each_fullref_in (get_main_ref_store (the_repository),"" , -hidden_refs_to_excludes (&hidden_refs), - show_ref_cb, &seen); + exclude_patterns, show_ref_cb, &seen);for_each_alternate_ref (show_one_alternate_ref, &seen); +oidset_clear (&seen); +strvec_clear (&excludes_vector); +if (!sent_capabilities)show_ref ("capabilities^{}" ,null_oid ());
t/t5509-fetch-push-namespaces.sh +8 -0
@@ -124,6 +124,14 @@ test_expect_success 'try to update a ref that is not hidden' ' git -C original push pushee-namespaced main ' +test_expect_success 'git-receive-pack(1) with transfer.hideRefs does not match unstripped refs during advertisement' ' + git -C pushee update-ref refs/namespaces/namespace/refs/heads/foo/1 refs/namespaces/namespace/refs/heads/main && + git -C pushee pack-refs --all && + test_config -C pushee transfer.hideRefs refs/namespaces/namespace/refs/heads/foo && + GIT_TRACE_PACKET="$(pwd)/trace" git -C original push pushee-namespaced main && + test_grep refs/heads/foo/1 trace +' + test_expect_success 'try to update a hidden full ref' ' test_config -C pushee transfer.hideRefs "^refs/namespaces/namespace/refs/heads/main" && test_must_fail git -C original push pushee-namespaced main
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
Re: [PATCH 2/6] builtin/receive-pack: fix exclude patterns when announcing refs
Patrick Steinhardt <[email protected]> writes:
[snip]
Quoted 11 lines
builtin/receive-pack.c +3
-0@@ -339,12 +339,26 @@ static void show_one_alternate_ref(const struct object_id *oid,static void write_head_info (void ) {static struct oidset seen =OIDSET_INIT ; +struct strvec excludes_vector =STRVEC_INIT ; +const char **exclude_patterns; +
builtin/receive-pack.c static void show_one_alternate_ref(const struct object_id *oid, · line 354
Quoted 10 lines
builtin/receive-pack.c +9
-0+/* +* We need access to the reference names both with and without their +* namespace and thus cannot use `refs_for_each_namespaced_ref()`. We +* thus have to adapt exclude patterns to carry the namespace prefix +* ourselves. +*/ + exclude_patterns =get_namespaced_exclude_patterns ( +hidden_refs_to_excludes (&hidden_refs), +get_git_namespace (), &excludes_vector);
Nit: So we do use it here, might be worth pointing out in the previous commit.
[snip]
PATCH 3/6 Makefile: stop listing test library objects twice
In reply to Patrick SteinhardtWhenever one adds another test library compilation unit one has to wire it up twice in the Makefile: once to append it to UNIT_TEST_OBJS, and once to append it to the UNIT_TEST_PROGS target. Ideally, we'd just reuse the UNIT_TEST_OBJS variable in the target so that we can avoid the duplication. But it also contains all the objects for our test programs, each of which contains a cmd_main(), and thus we cannot link them all into the target executable.
Refactor the code such that UNIT_TEST_OBJS does not contain the unit test program objects anymore, which we can instead manually append to the OBJECTS variable. Like this, the former variable now only contains objects for test libraries and can thus be reused.
--- Makefile | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-)
Makefile +2 -4
@@ -1356,7 +1356,6 @@ UNIT_TEST_PROGRAMS += t-strvec UNIT_TEST_PROGRAMS += t-trailer UNIT_TEST_PROGRAMS += t-urlmatch-normalization UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS)) -UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS)) UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-oid.o
@@ -2715,6 +2714,7 @@ OBJECTS += $(XDIFF_OBJS) OBJECTS += $(FUZZ_OBJS) OBJECTS += $(REFTABLE_OBJS) $(REFTABLE_TEST_OBJS) OBJECTS += $(UNIT_TEST_OBJS) +OBJECTS += $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS)) ifndef NO_CURL OBJECTS += http.o http-walker.o remote-curl.o
@@ -3852,9 +3852,7 @@ $(FUZZ_PROGRAMS): %: %.o oss-fuzz/dummy-cmd-main.o $(GITLIBS) GIT-LDFLAGS -Wl,--allow-multiple-definition \ $(filter %.o,$^) $(filter %.a,$^) $(LIBS) $(LIB_FUZZING_ENGINE) -$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o \ - $(UNIT_TEST_DIR)/test-lib.o \ - $(UNIT_TEST_DIR)/lib-oid.o \ +$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o $(UNIT_TEST_OBJS) \ $(GITLIBS) GIT-LDFLAGS $(call mkdir_p_parent_template) $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) \
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
PATCH 4/6 t/unit-tests: introduce reftable library
In reply to Patrick SteinhardtWe have recently migrated all of the reftable unit tests that were part of the reftable library into our own unit testing framework. As part of that migration we have duplicated some of the functionality that was part of the reftable test framework into each of the migrated test suites. This was a sensible decision to not have all of the migrations dependent on each other, but now that the migration is done it makes sense to deduplicate the functionality again.
Introduce a new reftable test library that hosts some shared code and adapt tests to use it.
--- Makefile | 1 + t/unit-tests/lib-reftable.c | 93 ++++++++++++++++++++ t/unit-tests/lib-reftable.h | 20 +++++ t/unit-tests/t-reftable-merged.c | 87 +++---------------- t/unit-tests/t-reftable-readwrite.c | 130 +++++++++------------------- t/unit-tests/t-reftable-stack.c | 25 +++--- 6 files changed, 177 insertions(+), 179 deletions(-) create mode 100644 t/unit-tests/lib-reftable.c create mode 100644 t/unit-tests/lib-reftable.h
Makefile +1 -0
@@ -1358,6 +1358,7 @@ UNIT_TEST_PROGRAMS += t-urlmatch-normalization UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS)) UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-oid.o +UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-reftable.o # xdiff and reftable libs may in turn depend on what is in libgit.a GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) $(LIB_FILE)
t/unit-tests/lib-reftable.c new file +93 -0
93 lines not on this page · raw message
t/unit-tests/lib-reftable.h new file +20 -0
@@ -0,0 +1,20 @@ +#ifndef LIB_REFTABLE_H +#define LIB_REFTABLE_H + +#include "git-compat-util.h" +#include "strbuf.h" +#include "reftable/reftable-writer.h" + +void t_reftable_set_hash (uint8_t *p,int i,uint32_t id); + +struct reftable_writer *t_reftable_strbuf_writer (struct strbuf *buf, +struct reftable_write_options *opts); + +void t_reftable_write_to_buf (struct strbuf *buf, +struct reftable_ref_record *refs, +size_t nrecords, +struct reftable_log_record *logs, +size_t nlogs, +struct reftable_write_options *opts); + +#endif
t/unit-tests/t-reftable-merged.c +11 -76
129 lines not on this page · raw message
t/unit-tests/t-reftable-readwrite.c +40 -90
246 lines not on this page · raw message
t/unit-tests/t-reftable-stack.c +12 -13
@@ -7,17 +7,13 @@ license that can be found in the LICENSE file or at*/ #include "test-lib.h" +#include "lib-reftable.h" #include "reftable/merged.h" #include "reftable/reader.h" #include "reftable/reftable-error.h" #include "reftable/stack.h" #include <dirent.h> -static void set_test_hash (uint8_t *p,int i) -{ -memset (p, (uint8_t )i,hash_size (GIT_SHA1_FORMAT_ID )); -} -static void clear_dir (const char *dirname) {struct strbuf path =STRBUF_INIT ;
@@ -125,7 +121,7 @@ static void write_n_ref_tables(struct reftable_stack *st,strbuf_reset (&buf);strbuf_addf (&buf,"refs/heads/branch-%04" PRIuMAX, (uintmax_t )i); ref.refname = buf.buf; -set_test_hash (ref.value.val1, i); +t_reftable_set_hash (ref.value.val1, i,GIT_SHA1_FORMAT_ID ); err =reftable_stack_add (st, &write_test_ref, &ref);check (!err);
@@ -470,13 +466,13 @@ static void t_reftable_stack_add(void) refs[i].refname =xstrdup (buf); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; -set_test_hash (refs[i].value.val1, i); +t_reftable_set_hash (refs[i].value.val1, i,GIT_SHA1_FORMAT_ID ); logs[i].refname =xstrdup (buf); logs[i].update_index =N + i +1 ; logs[i].value_type =REFTABLE_LOG_UPDATE ; logs[i].value.update.email =xstrdup ("identity@invalid" ); -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i,GIT_SHA1_FORMAT_ID ); }for (i =0 ; i <N ; i++) {
@@ -562,14 +558,14 @@ static void t_reftable_stack_iterator(void) refs[i].refname =xstrfmt ("branch%02" PRIuMAX, (uintmax_t )i); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; -set_test_hash (refs[i].value.val1, i); +t_reftable_set_hash (refs[i].value.val1, i,GIT_SHA1_FORMAT_ID ); logs[i].refname =xstrfmt ("branch%02" PRIuMAX, (uintmax_t )i); logs[i].update_index = i +1 ; logs[i].value_type =REFTABLE_LOG_UPDATE ; logs[i].value.update.email =xstrdup ("johndoe@invalid" ); logs[i].value.update.message =xstrdup ("commit\n" ); -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i,GIT_SHA1_FORMAT_ID ); }for (i =0 ; i <N ; i++) {
@@ -704,7 +700,8 @@ static void t_reftable_stack_tombstone(void) refs[i].update_index = i +1 ;if (i %2 ==0 ) { refs[i].value_type =REFTABLE_REF_VAL1 ; -set_test_hash (refs[i].value.val1, i); +t_reftable_set_hash (refs[i].value.val1, i, +GIT_SHA1_FORMAT_ID ); } logs[i].refname =xstrdup (buf);
@@ -712,7 +709,8 @@ static void t_reftable_stack_tombstone(void) logs[i].update_index =42 ;if (i %2 ==0 ) { logs[i].value_type =REFTABLE_LOG_UPDATE ; -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i, +GIT_SHA1_FORMAT_ID ); logs[i].value.update.email =xstrdup ("identity@invalid" ); }
@@ -844,7 +842,8 @@ static void t_reflog_expire(void) logs[i].value_type =REFTABLE_LOG_UPDATE ; logs[i].value.update.time = i; logs[i].value.update.email =xstrdup ("identity@invalid" ); -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i, +GIT_SHA1_FORMAT_ID ); }for (i =1 ; i <=N ; i++) {
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
PATCH 5/6 reftable/reader: make table iterator reseekable
In reply to Patrick SteinhardtIn 67ce50ba26 (Merge branch 'ps/reftable-reusable-iterator', 2024-05-30) we have refactored the interface of reftable iterators such that they can be reused in theory. This patch series only landed the required changes on the interface level, but didn't yet implement the actual logic to make iterators reusable.
As it turns out almost all of the infrastructure already does support re-seeking. The only exception is the table iterator, which does not reset its is_finished bit. Do so and add a couple of tests that verify that we can re-seek iterators.
--- Makefile | 1 + reftable/reader.c | 1 + t/unit-tests/t-reftable-merged.c | 76 +++++++++++++++++++++++++ t/unit-tests/t-reftable-reader.c | 96 ++++++++++++++++++++++++++++++++ 4 files changed, 174 insertions(+) create mode 100644 t/unit-tests/t-reftable-reader.c
Makefile +1 -0
@@ -1346,6 +1346,7 @@ UNIT_TEST_PROGRAMS += t-reftable-basics UNIT_TEST_PROGRAMS += t-reftable-block UNIT_TEST_PROGRAMS += t-reftable-merged UNIT_TEST_PROGRAMS += t-reftable-pq +UNIT_TEST_PROGRAMS += t-reftable-reader UNIT_TEST_PROGRAMS += t-reftable-readwrite UNIT_TEST_PROGRAMS += t-reftable-record UNIT_TEST_PROGRAMS += t-reftable-stack
reftable/reader.c +1 -0
@@ -328,6 +328,7 @@ static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ) ti->typ =block_reader_type (&ti->br); ti->block_off = off;block_iter_seek_start (&ti->bi, &ti->br); + ti->is_finished =0 ;return 0 ; }
t/unit-tests/t-reftable-merged.c +76 -0
88 lines not on this page · raw message
t/unit-tests/t-reftable-reader.c new file +96 -0
96 lines not on this page · raw message
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
Re: [PATCH 5/6] reftable/reader: make table iterator reseekable
Patrick Steinhardt <[email protected]> writes:
[snip]
Quoted 60 lines
t/unit-tests/t-reftable-merged.c +52
-0@@ -194,6 +194,81 @@ static void t_merged_refs(void)reftable_free (bs); } +static void t_merged_seek_multiple_times (void ) +{ +struct reftable_ref_record r1[] = { + { + .refname = (char *)"a" , + .update_index =1 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {1 }, + }, + { + .refname = (char *)"c" , + .update_index =1 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {2 }, + } + }; +struct reftable_ref_record r2[] = { + { + .refname = (char *)"b" , + .update_index =2 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {3 }, + }, + { + .refname = (char *)"d" , + .update_index =2 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {4 }, + }, + }; +struct reftable_ref_record *refs[] = { + r1, r2, + }; +size_t sizes[] = { +ARRAY_SIZE (r1),ARRAY_SIZE (r2), + }; +struct strbuf bufs[] = { +STRBUF_INIT ,STRBUF_INIT , + }; +struct reftable_block_source *sources =NULL ; +struct reftable_reader **readers =NULL ; +struct reftable_ref_record rec = {0 }; +struct reftable_iterator it = {0 }; +struct reftable_merged_table *mt; + + mt =merged_table_from_records (refs, &sources, &readers, sizes, bufs,2 ); +merged_table_init_iter (mt, &it,BLOCK_TYPE_REF ); + +for (size_t i =0 ; i <5 ; i++) { +int err =reftable_iterator_seek_ref (&it,"c" ); +check (!err); +
t/unit-tests/t-reftable-merged.c static void t_merged_refs(void) · line 258
Quoted 10 lines
t/unit-tests/t-reftable-merged.c +10
-0+ err =reftable_iterator_next_ref (&it, &rec); +check (!err); + err =reftable_ref_record_equal (&rec, &r1[1 ],GIT_SHA1_RAWSZ ); +check (err ==1 ); + + err =reftable_iterator_next_ref (&it, &rec); +check (!err); + err =reftable_ref_record_equal (&rec, &r2[1 ],GIT_SHA1_RAWSZ ); +check (err ==1 ); +
So this skips r2[0] because when we seek, we seek all sub-iterators. So in r2 we seek to 'd' since that is the next alphabetical value.
[snip]
Quoted 30 lines
t/unit-tests/t-reftable-reader.c new file +24
-0@@ -0,0 +1,96 @@ +#include "test-lib.h" +#include "lib-reftable.h" +#include "reftable/blocksource.h" +#include "reftable/reader.h" + +static int t_reader_seek_once (void ) +{ +struct reftable_ref_record records[] = { + { + .refname = (char *)"refs/heads/main" , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {42 }, + }, + }; +struct reftable_block_source source = {0 }; +struct reftable_ref_record ref = {0 }; +struct reftable_iterator it = {0 }; +struct reftable_reader *reader; +struct strbuf buf =STRBUF_INIT ; +int ret; + +t_reftable_write_to_buf (&buf, records,ARRAY_SIZE (records),NULL ,0 ,NULL ); +block_source_from_strbuf (&source, &buf); +
t/unit-tests/t-reftable-reader.c line 34
Quoted 10 lines
t/unit-tests/t-reftable-reader.c new file +10
-0+ ret =reftable_reader_new (&reader, &source,"name" ); + check_int(ret, ==, 0); + +reftable_reader_init_ref_iterator (reader, &it); + ret =reftable_iterator_seek_ref (&it,"" ); + check_int(ret, ==, 0); + ret =reftable_iterator_next_ref (&it, &ref); + check_int(ret, ==, 0); + + ret =reftable_ref_record_equal (&ref, &records[0 ],20 );
s/20/GIT_SHA1_RAWSZ
Also here and elsewhere, shouldn't we just docheck(reftable_ref_record_equal(...)) or even!check(reftable_iterator_seek_ref(...)) ?
[snip]
Re: [PATCH 5/6] reftable/reader: make table iterator reseekable
Quoted 35 lines · karthik nayak
Quoted 34 lines · Patrick Steinhardt
t/unit-tests/t-reftable-reader.c new file +28
-0@@ -0,0 +1,96 @@ +#include "test-lib.h" +#include "lib-reftable.h" +#include "reftable/blocksource.h" +#include "reftable/reader.h" + +static int t_reader_seek_once (void ) +{ +struct reftable_ref_record records[] = { + { + .refname = (char *)"refs/heads/main" , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {42 }, + }, + }; +struct reftable_block_source source = {0 }; +struct reftable_ref_record ref = {0 }; +struct reftable_iterator it = {0 }; +struct reftable_reader *reader; +struct strbuf buf =STRBUF_INIT ; +int ret; + +t_reftable_write_to_buf (&buf, records,ARRAY_SIZE (records),NULL ,0 ,NULL ); +block_source_from_strbuf (&source, &buf); + + ret =reftable_reader_new (&reader, &source,"name" ); + check_int(ret, ==, 0); + +reftable_reader_init_ref_iterator (reader, &it);
Quoted 8 lines
t/unit-tests/t-reftable-reader.c line 34
Quoted 6 lines
t/unit-tests/t-reftable-reader.c new file +6
-0+ ret =reftable_iterator_seek_ref (&it,"" ); + check_int(ret, ==, 0); + ret =reftable_iterator_next_ref (&it, &ref); + check_int(ret, ==, 0); + + ret =reftable_ref_record_equal (&ref, &records[0 ],20 );s/20/GIT_SHA1_RAWSZ
Indeed.
Quoted 3 lines
Also here and elsewhere, shouldn't we just do
check(reftable_ref_record_equal(...))or even!check(reftable_iterator_seek_ref(...))?
I guess you mean check(!reftable_iteraror_seek_ref()), right?
In the case where we just expect a zero error code I can certainly adapt the code to use check(...). But the other cases shouldn't use check(!...) because it is important that the returnd error code is positive.
Patrick
Re: [PATCH 5/6] reftable/reader: make table iterator reseekable
Quoted 45 lines · Patrick Steinhardt
Quoted 35 lines · karthik nayak
Quoted 34 lines · Patrick Steinhardt
t/unit-tests/t-reftable-reader.c new file +28
-0@@ -0,0 +1,96 @@ +#include "test-lib.h" +#include "lib-reftable.h" +#include "reftable/blocksource.h" +#include "reftable/reader.h" + +static int t_reader_seek_once (void ) +{ +struct reftable_ref_record records[] = { + { + .refname = (char *)"refs/heads/main" , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = {42 }, + }, + }; +struct reftable_block_source source = {0 }; +struct reftable_ref_record ref = {0 }; +struct reftable_iterator it = {0 }; +struct reftable_reader *reader; +struct strbuf buf =STRBUF_INIT ; +int ret; + +t_reftable_write_to_buf (&buf, records,ARRAY_SIZE (records),NULL ,0 ,NULL ); +block_source_from_strbuf (&source, &buf); + + ret =reftable_reader_new (&reader, &source,"name" ); + check_int(ret, ==, 0); + +reftable_reader_init_ref_iterator (reader, &it);Quoted 8 lines
t/unit-tests/t-reftable-reader.c line 34
Quoted 6 lines
t/unit-tests/t-reftable-reader.c new file +6
-0+ ret =reftable_iterator_seek_ref (&it,"" ); + check_int(ret, ==, 0); + ret =reftable_iterator_next_ref (&it, &ref); + check_int(ret, ==, 0); + + ret =reftable_ref_record_equal (&ref, &records[0 ],20 );s/20/GIT_SHA1_RAWSZ
Quoted 8 lines
Indeed.
Quoted 3 lines
Also here and elsewhere, shouldn't we just do
check(reftable_ref_record_equal(...))or even!check(reftable_iterator_seek_ref(...))?I guess you mean
check(!reftable_iteraror_seek_ref()), right?
Yes.
Quoted 5 lines
In the case where we just expect a zero error code I can certainly adapt the code to use
check(...). But the other cases shouldn't usecheck(!...)because it is important that the returnd error code is positive.
Perfect!
Quoted 1 line
Patrick
Karthik
PATCH 6/6 refs/reftable: wire up support for exclude patterns
In reply to Patrick SteinhardtExclude patterns can be used by reference backends to skip over blocks of references that are uninteresting to the caller. Reference backends do not have to wire up support for them, and all callers are expected to behave as if the backend didn't support them. In fact, the only backend that supports exclude patterns right now is the "packed" backend.
Exclude patterns can be quite an important performance optimization in repositories that have loads of references. The patterns are set up in case "transfer.hideRefs" and friends are configured during a fetch, so handling these patterns becomes important once there are lots of hidden refs in a served repository.
Now that we have properly re-seekable reftable iterators we can also wire up support for these patterns in the "reftable" backend. Doing so is conceptually simple: once we hit a reference whose prefix matches the current exclude pattern we re-seek the iterator to the first reference that doesn't match the pattern anymore. This schema only works for trivial patterns that do not have any globbing characters in them, but this restriction also applies do the "packed" backend.
This makes t1419 work with the "reftable" backend with some slight modifications. Of course it also speeds up listing of references with hidden refs. The following benchmark prints one reference with 1 million hidden references:
Benchmark 1: HEAD~
Time (mean ± σ): 93.3 ms ± 2.1 ms [User: 90.3 ms, System: 2.5 ms]
Range (min … max): 89.8 ms … 97.2 ms 33 runs
Benchmark 2: HEAD
Time (mean ± σ): 4.2 ms ± 0.6 ms [User: 2.2 ms, System: 1.8 ms]
Range (min … max): 3.1 ms … 8.1 ms 765 runs
Summary
HEAD ran
22.15 ± 3.19 times faster than HEAD~
--- refs/reftable-backend.c | 125 +++++++++++++++++++++++++++++++++++++++- t/t1419-exclude-refs.sh | 33 ++++++++--- trace2.h | 1 + trace2/tr2_ctr.c | 5 ++ 4 files changed, 152 insertions(+), 12 deletions(-)
refs/reftable-backend.c +122 -3
@@ -21,6 +21,7 @@#include "../reftable/reftable-iterator.h" #include "../setup.h" #include "../strmap.h" +#include "../trace2.h" #include "parse.h" #include "refs-internal.h"
@@ -447,10 +448,81 @@ struct reftable_ref_iterator {const char *prefix;size_t prefix_len; +char **exclude_patterns; +size_t exclude_patterns_index; +size_t exclude_patterns_strlen;unsigned int flags;int err; }; +/* +* Handle exclude patterns. Returns either `1`, which tells the caller that the +* current reference shall not be shown. Or `0`, which indicates that it should +* be shown. +*/ +static int should_exclude_current_ref (struct reftable_ref_iterator *iter) +{ +while (iter->exclude_patterns[iter->exclude_patterns_index]) { +const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index]; +char *ref_after_pattern; +int cmp; + +/* +* Lazily cache the pattern length so that we don't have to +* recompute it every time this function is called. +*/ +if (!iter->exclude_patterns_strlen) + iter->exclude_patterns_strlen =strlen (pattern); + +/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches. +* +* Otherwise, if it's smaller, then we do not have a match and +* thus want to show the current reference. +*/ + cmp =strncmp (iter->ref.refname, pattern, + iter->exclude_patterns_strlen); +if (cmp >0 ) { + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +continue ; + } +if (cmp <0 ) +return 0 ; + +/* +* The reference shares a prefix with the exclude pattern and +* shall thus be omitted. We skip all references that match the +* pattern by seeking to the first reference after the block of +* matches. +* +* This is done by appending the highest possible character to +* the pattern. Consequently, all references that have the +* pattern as prefix and whose suffix starts with anything in +* the range [0x00, 0xfe] are skipped. And given that 0xff is a +* non-printable character that shouldn't ever be in a ref name, +* we'd not yield any such record, either. +* +* Note that the seeked-to reference may also be excluded. This +* is not handled here though, but the caller is expected to +* loop and re-verify the next reference for us. +*/ + ref_after_pattern =xstrfmt ("%s%c" , pattern,0xff ); + iter->err =reftable_iterator_seek_ref (&iter->iter, ref_after_pattern); + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +trace2_counter_add (TRACE2_COUNTER_ID_REFTABLE_RESEEKS ,1 ); + +free (ref_after_pattern); +return 1 ; + } + +return 0 ; +} +static int reftable_ref_iterator_advance (struct ref_iterator *ref_iterator) { struct reftable_ref_iterator *iter =
@@ -481,6 +553,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)break ; } +if (iter->exclude_patterns &&should_exclude_current_ref (iter)) +continue ; +if (iter->flags &DO_FOR_EACH_PER_WORKTREE_ONLY &&parse_worktree_ref (iter->ref.refname,NULL ,NULL ,NULL ) !=REF_WORKTREE_CURRENT )
@@ -570,6 +645,11 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) (struct reftable_ref_iterator *)ref_iterator;reftable_ref_record_release (&iter->ref);reftable_iterator_destroy (&iter->iter); +if (iter->exclude_patterns) { +for (size_t i =0 ; iter->exclude_patterns[i]; i++) +free (iter->exclude_patterns[i]); +free (iter->exclude_patterns); + }free (iter);return ITER_DONE ; }
@@ -580,9 +660,45 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .abort = reftable_ref_iterator_abort }; +static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i]; +int has_glob =0 ; + +if (!exclude_pattern) +break ; + +for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + } +if (has_glob) +continue ; + +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =xstrdup (exclude_pattern); + } + +if (filtered_size) { +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =NULL ; + } + +return filtered; +} +static struct reftable_ref_iterator *ref_iterator_for_stack (struct reftable_ref_store *refs,struct reftable_stack *stack,const char *prefix, +const char **exclude_patterns,int flags) {struct reftable_ref_iterator *iter;
@@ -595,6 +711,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ iter->base.oid = &iter->oid; iter->flags = flags; iter->refs = refs; + iter->exclude_patterns =filter_exclude_patterns (exclude_patterns); ret = refs->err;if (ret)
@@ -616,7 +733,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_static struct ref_iterator *reftable_be_iterator_begin (struct ref_store *ref_store,const char *prefix, - const char **exclude_patterns UNUSED, +const char **exclude_patterns,unsigned int flags) {struct reftable_ref_iterator *main_iter, *worktree_iter;
@@ -627,7 +744,8 @@ static struct ref_iterator *reftable_be_iterator_begin(struct ref_store *ref_sto required_flags |=REF_STORE_ODB ; refs =reftable_be_downcast (ref_store, required_flags,"ref_iterator_begin" ); - main_iter =ref_iterator_for_stack (refs, refs->main_stack, prefix, flags); + main_iter =ref_iterator_for_stack (refs, refs->main_stack, prefix, + exclude_patterns, flags);/* * The worktree stack is only set when we're in an actual worktree
@@ -641,7 +759,8 @@ static struct ref_iterator *reftable_be_iterator_begin(struct ref_store *ref_sto* Otherwise we merge both the common and the per-worktree refs into a * single iterator. */ - worktree_iter =ref_iterator_for_stack (refs, refs->worktree_stack, prefix, flags); + worktree_iter =ref_iterator_for_stack (refs, refs->worktree_stack, prefix, + exclude_patterns, flags);return merge_ref_iterator_begin (&worktree_iter->base, &main_iter->base, ref_iterator_select,NULL ); }
t/t1419-exclude-refs.sh +24 -9
@@ -8,12 +8,6 @@ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME TEST_PASSES_SANITIZE_LEAK=true . ./test-lib.sh -if test_have_prereq !REFFILES -then - skip_all='skipping `git for-each-ref --exclude` tests; need files backend' - test_done -fi - for_each_ref__exclude () { GIT_TRACE2_PERF=1 test-tool ref-store main \ for-each-ref--exclude "$@" >actual.raw
@@ -28,7 +22,14 @@ assert_jumps () { local nr="$1" local trace="$2" - grep -q "name:jumps_made value:$nr$" $trace + case "$GIT_DEFAULT_REF_FORMAT" in + files) + grep -q "name:jumps_made value:$nr$" $trace;; + reftable) + grep -q "name:reseeks_made value:$nr$" $trace;; + *) + BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";; + esac } assert_no_jumps () {
@@ -89,7 +90,14 @@ test_expect_success 'adjacent, non-overlapping excluded regions' ' for_each_ref refs/heads/foo refs/heads/quux >expect && test_cmp expect actual && - assert_jumps 1 perf + case "$GIT_DEFAULT_REF_FORMAT" in + files) + assert_jumps 1 perf;; + reftable) + assert_jumps 2 perf;; + *) + BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";; + esac ' test_expect_success 'overlapping excluded regions' '
@@ -106,7 +114,14 @@ test_expect_success 'several overlapping excluded regions' ' for_each_ref refs/heads/quux >expect && test_cmp expect actual && - assert_jumps 1 perf + case "$GIT_DEFAULT_REF_FORMAT" in + files) + assert_jumps 1 perf;; + reftable) + assert_jumps 3 perf;; + *) + BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";; + esac ' test_expect_success 'non-matching excluded section' '
trace2.h +1 -0
@@ -554,6 +554,7 @@ enum trace2_counter_id {TRACE2_COUNTER_ID_TEST2 ,/* emits summary and thread events */ TRACE2_COUNTER_ID_PACKED_REFS_JUMPS ,/* counts number of jumps */ +TRACE2_COUNTER_ID_REFTABLE_RESEEKS ,/* counts number of re-seeks */ /* counts number of fsyncs */ TRACE2_COUNTER_ID_FSYNC_WRITEOUT_ONLY,
trace2/tr2_ctr.c +5 -0
@@ -31,6 +31,11 @@ static struct tr2_counter_metadata tr2_counter_metadata[TRACE2_NUMBER_OF_COUNTER .name = "jumps_made", .want_per_thread_events = 0, }, + [TRACE2_COUNTER_ID_REFTABLE_RESEEKS] = { + .category = "reftable", + .name = "reseeks_made", + .want_per_thread_events = 0, + }, [TRACE2_COUNTER_ID_FSYNC_WRITEOUT_ONLY] = { .category = "fsync", .name = "writeout-only",
Signature · 1 line
2.46.0.519.g2e7b89e038.dirty
Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns
Patrick Steinhardt <[email protected]> writes:
[snip]
Quoted 7 lines
hidden refs. The following benchmark prints one reference with 1 million hidden references:
Benchmark 1: HEAD~
Time (mean ± σ): 93.3 ms ± 2.1 ms [User: 90.3 ms, System: 2.5 ms]
Range (min … max): 89.8 ms … 97.2 ms 33 runs
Quoted 8 lines
Benchmark 2: HEAD
Time (mean ± σ): 4.2 ms ± 0.6 ms [User: 2.2 ms, System: 1.8 ms]
Range (min … max): 3.1 ms … 8.1 ms 765 runsSummary
HEAD ran
22.15 ± 3.19 times faster than HEAD~
Nice.
Quoted 45 lines
Signed-off-by Patrick Steinhardt <[email protected]>--- refs/reftable-backend.c | 125 +++++++++++++++++++++++++++++++++++++++- t/t1419-exclude-refs.sh | 33 ++++++++--- trace2.h | 1 + trace2/tr2_ctr.c | 5 ++ 4 files changed, 152 insertions(+), 12 deletions(-)refs/reftable-backend.c +18
-0@@ -21,6 +21,7 @@#include "../reftable/reftable-iterator.h" #include "../setup.h" #include "../strmap.h" +#include "../trace2.h" #include "parse.h" #include "refs-internal.h" @@ -447,10 +448,81 @@ struct reftable_ref_iterator {const char *prefix;size_t prefix_len; +char **exclude_patterns; +size_t exclude_patterns_index; +size_t exclude_patterns_strlen;unsigned int flags;int err; }; +/* +* Handle exclude patterns. Returns either `1`, which tells the caller that the +* current reference shall not be shown. Or `0`, which indicates that it should +* be shown. +*/ +static int should_exclude_current_ref (struct reftable_ref_iterator *iter) +{ +while (iter->exclude_patterns[iter->exclude_patterns_index]) { +const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index]; +char *ref_after_pattern; +int cmp; + +/* +* Lazily cache the pattern length so that we don't have to
refs/reftable-backend.c struct reftable_ref_iterator { · line 481
Quoted 10 lines
refs/reftable-backend.c +10
-0+* recompute it every time this function is called. +*/ +if (!iter->exclude_patterns_strlen) + iter->exclude_patterns_strlen =strlen (pattern); + +/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches.
So this means that the exclude patterns were lexicographically sorted. Otherwise this would work.
Quoted 16 lines
refs/reftable-backend.c +16
-0+* Otherwise, if it's smaller, then we do not have a match and +* thus want to show the current reference. +*/ + cmp =strncmp (iter->ref.refname, pattern, + iter->exclude_patterns_strlen); +if (cmp >0 ) { + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +continue ; + } +if (cmp <0 ) +return 0 ; + +/* +* The reference shares a prefix with the exclude pattern and +* shall thus be omitted. We skip all references that match the
refs/reftable-backend.c struct reftable_ref_iterator { · line 508
Quoted 10 lines
refs/reftable-backend.c +10
-0+* pattern by seeking to the first reference after the block of +* matches. +* +* This is done by appending the highest possible character to +* the pattern. Consequently, all references that have the +* pattern as prefix and whose suffix starts with anything in +* the range [0x00, 0xfe] are skipped. And given that 0xff is a +* non-printable character that shouldn't ever be in a ref name, +* we'd not yield any such record, either. +*
This is simple yet clever.
refs/reftable-backend.c struct reftable_ref_iterator { · line 512
Quoted 4 lines
refs/reftable-backend.c +4
-0+* Note that the seeked-to reference may also be excluded. This +* is not handled here though, but the caller is expected to +* loop and re-verify the next reference for us. +*/
The seeked-to reference here being the one with 0xff. We could get rid of this by doing something like this:
int last_char_idx = iter->exclude_patterns_strlen - 1
ref_after_pattern = xstrfmt("%s", pattern);
ref_after_pattern[last_char_idx] = ref_after_pattern[last_char_idx] + 1;instead no?
Quoted 52 lines
refs/reftable-backend.c +31
-0+ ref_after_pattern =xstrfmt ("%s%c" , pattern,0xff ); + iter->err =reftable_iterator_seek_ref (&iter->iter, ref_after_pattern); + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +trace2_counter_add (TRACE2_COUNTER_ID_REFTABLE_RESEEKS ,1 ); + +free (ref_after_pattern); +return 1 ; + } + +return 0 ; +} +static int reftable_ref_iterator_advance (struct ref_iterator *ref_iterator) { struct reftable_ref_iterator *iter =@@ -481,6 +553,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)break ; } +if (iter->exclude_patterns &&should_exclude_current_ref (iter)) +continue ; +if (iter->flags &DO_FOR_EACH_PER_WORKTREE_ONLY &&parse_worktree_ref (iter->ref.refname,NULL ,NULL ,NULL ) !=REF_WORKTREE_CURRENT )@@ -570,6 +645,11 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) (struct reftable_ref_iterator *)ref_iterator;reftable_ref_record_release (&iter->ref);reftable_iterator_destroy (&iter->iter); +if (iter->exclude_patterns) { +for (size_t i =0 ; iter->exclude_patterns[i]; i++) +free (iter->exclude_patterns[i]); +free (iter->exclude_patterns); + }free (iter);return ITER_DONE ; }@@ -580,9 +660,45 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .abort = reftable_ref_iterator_abort }; +static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i];
refs/reftable-backend.c static struct ref_iterator_vtable reftable_ref_iterator_vtable = { · line 682
Quoted 10 lines
refs/reftable-backend.c +10
-0+int has_glob =0 ; + +if (!exclude_pattern) +break ; + +for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + }
Why do we need to filter excludes here? Don't the callee's already do something like this?
[snip]
Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns
Quoted 20 lines · karthik nayak
Quoted 19 lines · Patrick Steinhardt
refs/reftable-backend.c +19
-0+/* +* Handle exclude patterns. Returns either `1`, which tells the caller that the +* current reference shall not be shown. Or `0`, which indicates that it should +* be shown. +*/ +static int should_exclude_current_ref (struct reftable_ref_iterator *iter) +{ +while (iter->exclude_patterns[iter->exclude_patterns_index]) { +const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index]; +char *ref_after_pattern; +int cmp; + +/* +* Lazily cache the pattern length so that we don't have to +* recompute it every time this function is called. +*/ +if (!iter->exclude_patterns_strlen) + iter->exclude_patterns_strlen =strlen (pattern); +
Quoted 8 lines
refs/reftable-backend.c struct reftable_ref_iterator { · line 481
Quoted 5 lines
refs/reftable-backend.c +5
-0+/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches. So this means that the exclude patterns were lexicographically sorted. Otherwise this would work.
Indeed. Good that you call out my assumption, as I in fact didn't verify that it holds, and in fact it doesn't. It's not a correctness issue if it doesn't hold, because it would simply mean that we don't skip over some references where we really could. But it certainly is a perfomance issue.
Will fix and add a test for it.
Quoted 8 lines
refs/reftable-backend.c struct reftable_ref_iterator { · line 512
Quoted 4 lines
refs/reftable-backend.c +4
-0+* Note that the seeked-to reference may also be excluded. This +* is not handled here though, but the caller is expected to +* loop and re-verify the next reference for us. +*/ The seeked-to reference here being the one with
0xff. We could get rid of this by doing something like this:
Quoted 5 lines
int last_char_idx = iter->exclude_patterns_strlen - 1 ref_after_pattern = xstrfmt("%s", pattern); ref_after_pattern[last_char_idx] = ref_after_pattern[last_char_idx] + 1;instead no?
Sorry, I don't quite follow what you mean with "get rid of this". What exactly is "this"? Do you mean the re-looping?
If so then the above doesn't fix it, no. We'd have to repeat a whole lot of code here to also retrieve the next entry, store it into iter->ref, check whether it is an actual ref starting with "refs/" and so on. Looping once very much feels like the better thing to do.
Quoted 19 lines
Quoted 19 lines
refs/reftable-backend.c +15
-0@@ -580,9 +660,45 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .abort = reftable_ref_iterator_abort }; +static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i]; +int has_glob =0 ; + +if (!exclude_pattern) +break ; +
Quoted 8 lines
refs/reftable-backend.c static struct ref_iterator_vtable reftable_ref_iterator_vtable = { · line 682
Quoted 5 lines
refs/reftable-backend.c +5
-0+for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + }Why do we need to filter excludes here? Don't the callee's already do something like this?
No, it doesn't. The code for exclude patterns is structured in such a way that the responsibility is with the backend to decide what it can and cannot filter. In theory there could be a backend that can exclude refs based on globs efficiently, even though neither the "files" nor the "reftable" backend can.
Patrick
Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns
Quoted 52 lines · Patrick Steinhardt
Quoted 20 lines · karthik nayak
Quoted 19 lines · Patrick Steinhardt
refs/reftable-backend.c +19
-0+/* +* Handle exclude patterns. Returns either `1`, which tells the caller that the +* current reference shall not be shown. Or `0`, which indicates that it should +* be shown. +*/ +static int should_exclude_current_ref (struct reftable_ref_iterator *iter) +{ +while (iter->exclude_patterns[iter->exclude_patterns_index]) { +const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index]; +char *ref_after_pattern; +int cmp; + +/* +* Lazily cache the pattern length so that we don't have to +* recompute it every time this function is called. +*/ +if (!iter->exclude_patterns_strlen) + iter->exclude_patterns_strlen =strlen (pattern); +Quoted 8 lines
refs/reftable-backend.c struct reftable_ref_iterator { · line 481
Quoted 5 lines
refs/reftable-backend.c +5
-0+/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches. So this means that the exclude patterns were lexicographically sorted. Otherwise this would work.
Indeed. Good that you call out my assumption, as I in fact didn't verify that it holds, and in fact it doesn't. It's not a correctness issue if it doesn't hold, because it would simply mean that we don't skip over some references where we really could. But it certainly is a perfomance issue.
Will fix and add a test for it.
Quoted 8 lines
refs/reftable-backend.c struct reftable_ref_iterator { · line 512
Quoted 4 lines
refs/reftable-backend.c +4
-0+* Note that the seeked-to reference may also be excluded. This +* is not handled here though, but the caller is expected to +* loop and re-verify the next reference for us. +*/ The seeked-to reference here being the one with
0xff. We could get rid of this by doing something like this:Quoted 5 lines
int last_char_idx = iter->exclude_patterns_strlen - 1 ref_after_pattern = xstrfmt("%s", pattern); ref_after_pattern[last_char_idx] = ref_after_pattern[last_char_idx] + 1;instead no?
Quoted 8 lines
Sorry, I don't quite follow what you mean with "get rid of this". What exactly is "this"? Do you mean the re-looping?
If so then the above doesn't fix it, no. We'd have to repeat a whole lot of code here to also retrieve the next entry, store it into
iter->ref, check whether it is an actual ref starting with "refs/" and so on. Looping once very much feels like the better thing to do.
I definitely responded to the wrong chunk of your comment. I meant to respond to
Quoted 6 lines
* This is done by appending the highest possible character to
* the pattern. Consequently, all references that have the
* pattern as prefix and whose suffix starts with anything in
* the range [0x00,0xfe] are skipped. And given that0xffis a
* non-printable character that shouldn't ever be in a ref name,
* we'd not yield any such record, either.
My point being, we can even skip "pattern + 0xff" by just setting the seek to ref to be the next character in the pattern. But since "pattern
+ 0xff" is anyways not an expected ref. They should behave the same.
Quoted 28 lines
Quoted 19 lines
Quoted 19 lines
refs/reftable-backend.c +15
-0@@ -580,9 +660,45 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .abort = reftable_ref_iterator_abort }; +static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i]; +int has_glob =0 ; + +if (!exclude_pattern) +break ; +Quoted 8 lines
refs/reftable-backend.c static struct ref_iterator_vtable reftable_ref_iterator_vtable = { · line 682
Quoted 5 lines
refs/reftable-backend.c +5
-0+for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + }Why do we need to filter excludes here? Don't the callee's already do something like this?
Quoted 5 lines
No, it doesn't. The code for exclude patterns is structured in such a way that the responsibility is with the backend to decide what it can and cannot filter. In theory there could be a backend that can exclude refs based on globs efficiently, even though neither the "files" nor the "reftable" backend can.
Thanks for the explanataion.
Quoted 22 lines · Patrick Steinhardt
Hi,
this patch series wires up exclude patterns for the reftable backend. Exclude patterns allow the backend to skip references internally that match a specific pattern. This avoids having to read references that the caller would discard immediately anyway.
The series is structured as follows:
- Patches 1 and 2 fix two separate bugs in how we currently handle exclude patterns in combination with namespaces. We didn't happen to stumble over these bugs before because exclude patterns are only implemented for the "packed" backend. But once you start to pack refs we exclude references based on their full name instead of the name with the prefixed stripped. For the reftable backend we'd always hit those bugs because it always uses exclude patterns when passed.
- Patches 3 to 5 wire up proper re-seeking of reftable iterators and adds some tests to demonstrate that this works as expected. This is a prerequisite for handling exclude patterns.
Quoted 7 lines
- Patch 6 wires up exclude patterns in the reftable backend by re-seeking iterators once we hit an excluded reference.
Thanks!
Patrick
This was a bit more intensive so I took my time with the review. Overall I have some questions/comments. But the series looks good. Thanks!
Karthik
Quoted 27 lines · karthik nayak
Quoted 25 lines · Patrick Steinhardt
Hi,
this patch series wires up exclude patterns for the reftable backend. Exclude patterns allow the backend to skip references internally that match a specific pattern. This avoids having to read references that the caller would discard immediately anyway.
The series is structured as follows:
- Patches 1 and 2 fix two separate bugs in how we currently handle exclude patterns in combination with namespaces. We didn't happen to stumble over these bugs before because exclude patterns are only implemented for the "packed" backend. But once you start to pack refs we exclude references based on their full name instead of the name with the prefixed stripped. For the reftable backend we'd always hit those bugs because it always uses exclude patterns when passed.
- Patches 3 to 5 wire up proper re-seeking of reftable iterators and adds some tests to demonstrate that this works as expected. This is a prerequisite for handling exclude patterns.
- Patch 6 wires up exclude patterns in the reftable backend by re-seeking iterators once we hit an excluded reference.
Quoted 7 lines
Quoted 4 lines
Thanks!
Patrick
This was a bit more intensive so I took my time with the review. Overall I have some questions/comments. But the series looks good. Thanks!
Thanks for your review!
Patrick
v2 cover refs/reftable: wire up exclude patterns
In reply to Patrick SteinhardtHi,
this is the second version of my patch series that fixes preexisting bugs with exclude patterns and wires them up for the reftable backend.
Changes compared to v1:
- Some typo fixes in commit messages.
- Mention that the newly introduced function in patch 1 will be used in patch 2, which is why it's declared in "refs.h".
- Use check() instead of check_int(ret, ==, 0).
- Sort exclude patterns lexicographically. This fixes a bug where we might not correctly skip over some refs when patterns are passed to the reftable backend in non-lexicographic order. Add a test for this.
Thanks!
Patrick
Patrick Steinhardt (6):
refs: properly apply exclude patterns to namespaced refs builtin/receive-pack: fix exclude patterns when announcing refs
Makefile: stop listing test library objects twice t/unit-tests: introduce reftable library reftable/reader: make table iterator reseekable refs/reftable: wire up support for exclude patterns
Makefile | 8 +- builtin/receive-pack.c | 18 ++- refs.c | 35 +++++- refs.h | 9 ++ refs/reftable-backend.c | 133 ++++++++++++++++++++++- reftable/reader.c | 1 + t/t1419-exclude-refs.sh | 49 +++++++-- t/t5509-fetch-push-namespaces.sh | 9 ++ t/unit-tests/lib-reftable.c | 93 ++++++++++++++++ t/unit-tests/lib-reftable.h | 20 ++++ t/unit-tests/t-reftable-merged.c | 163 +++++++++++++++------------- t/unit-tests/t-reftable-reader.c | 96 ++++++++++++++++ t/unit-tests/t-reftable-readwrite.c | 130 +++++++--------------- t/unit-tests/t-reftable-stack.c | 25 ++--- trace2.h | 1 + trace2/tr2_ctr.c | 5 + 16 files changed, 594 insertions(+), 201 deletions(-) create mode 100644 t/unit-tests/lib-reftable.c create mode 100644 t/unit-tests/lib-reftable.h create mode 100644 t/unit-tests/t-reftable-reader.c
Range-diff against v1:
1: 8d347bc5599 ! 1: 7497166422e refs: properly apply exclude patterns to namespaced refs
@@ Commit message
to the non-stripped ones that still have the namespace prefix. In fact, the "transfer.hideRefs" machinery does the former and applies to the stripped reference by default, but rules can have "^" prefixed to switch
- this behaviour to iinstead match against the rull reference name.
+ this behaviour to instead match against the full reference name.
Namespaces are exclusively handled at the generic "refs" layer, the respective backends have no clue that such a thing even exists. This
@@ Commit message
refs in the tests, and then we indeed surface the breakage.
Fix this bug by prefixing exclude patterns with the namespace in the
- generic layer.
+ generic layer. The newly introduced function will be used outside of
+ "refs.c" in the next patch, so we add a declaration to "refs.h".
2: 0317a5a7ede = 2: 3dc6ae936c8 builtin/receive-pack: fix exclude patterns when announcing refs
3: 503c44e6cab = 3: 4ba503520e6 Makefile: stop listing test library objects twice
4: 3df4040dd3c = 4: 6747076420f t/unit-tests: introduce reftable library
5: a281f936a2b ! 5: 3278cdf92fe reftable/reader: make table iterator reseekable
@@ t/unit-tests/t-reftable-reader.c (new)
+ block_source_from_strbuf(&source, &buf);
+
+ ret = reftable_reader_new(&reader, &source, "name");
-+ check_int(ret, ==, 0);
++ check(!ret);
+
+ reftable_reader_init_ref_iterator(reader, &it);
+ ret = reftable_iterator_seek_ref(&it, "");
-+ check_int(ret, ==, 0);
++ check(!ret);
+ ret = reftable_iterator_next_ref(&it, &ref);
-+ check_int(ret, ==, 0);
++ check(!ret);
+
-+ ret = reftable_ref_record_equal(&ref, &records[0], 20);
++ ret = reftable_ref_record_equal(&ref, &records[0], GIT_SHA1_RAWSZ);
+ check_int(ret, ==, 1);
+
+ ret = reftable_iterator_next_ref(&it, &ref);
@@ t/unit-tests/t-reftable-reader.c (new)
+ block_source_from_strbuf(&source, &buf);
+
+ ret = reftable_reader_new(&reader, &source, "name");
-+ check_int(ret, ==, 0);
++ check(!ret);
+
+ reftable_reader_init_ref_iterator(reader, &it);
+
+ for (size_t i = 0; i < 5; i++) {
+ ret = reftable_iterator_seek_ref(&it, "");
-+ check_int(ret, ==, 0);
++ check(!ret);
+ ret = reftable_iterator_next_ref(&it, &ref);
-+ check_int(ret, ==, 0);
++ check(!ret);
+
+ ret = reftable_ref_record_equal(&ref, &records[0], GIT_SHA1_RAWSZ);
+ check_int(ret, ==, 1);
6: f3922b81db6 ! 6: 050f4906393 refs/reftable: wire up support for exclude patterns
@@ refs/reftable-backend.c: static struct ref_iterator_vtable reftable_ref_iterator
.abort = reftable_ref_iterator_abort
};
++static int qsort_strcmp(const void *va, const void *vb)
++{
++ const char *a = *(const char **)va;
++ const char *b = *(const char **)vb;
++ return strcmp(a, b);
++}
++
+static char **filter_exclude_patterns(const char **exclude_patterns)
+{
+ size_t filtered_size = 0, filtered_alloc = 0;
@@ refs/reftable-backend.c: static struct ref_iterator_vtable reftable_ref_iterator
+ }
+
+ if (filtered_size) {
++ QSORT(filtered, filtered_size, qsort_strcmp);
+ ALLOC_GROW(filtered, filtered_size + 1, filtered_alloc);
+ filtered[filtered_size++] = NULL;
+ }
@@ t/t1419-exclude-refs.sh: test_expect_success 'several overlapping excluded regio
+ assert_jumps 3 perf;;
+ *)
+ BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";;
++ esac
++'
++
++test_expect_success 'unordered excludes' '
++ for_each_ref__exclude refs/heads \
++ refs/heads/foo refs/heads/baz >actual 2>perf &&
++ for_each_ref refs/heads/bar refs/heads/quux >expect &&
++
++ test_cmp expect actual &&
++ case "$GIT_DEFAULT_REF_FORMAT" in
++ files)
++ assert_jumps 1 perf;;
++ reftable)
++ assert_jumps 2 perf;;
++ *)
++ BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";;
+ esac
'Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
PATCH v2 1/6 refs: properly apply exclude patterns to namespaced refs
Reference namespaces allow commands like git-upload-pack(1) to serve different sets of references to the client depending on which namespace is enabled, which is for example useful in fork networks. Namespaced refs are stored with a refs/namespaces/$namespace prefix, but all the user will ultimately see is a stripped version where that prefix is removed.
The way that this interacts with "transfer.hideRefs" is not immediately
obvious: the hidden refs can either apply to the stripped references, or to the non-stripped ones that still have the namespace prefix. In fact, the "transfer.hideRefs" machinery does the former and applies to the stripped reference by default, but rules can have "^" prefixed to switch this behaviour to instead match against the full reference name.
Namespaces are exclusively handled at the generic "refs" layer, the respective backends have no clue that such a thing even exists. This also has the consequence that they cannot handle hiding references as soon as reference namespaces come into play because they neither know whether a namespace is active, nor do they know how to strip references if they are active.
Handling such exclude patterns in refs_for_each_namespaced_ref() and refs_for_each_fullref_in_prefixes() is broken though, as both support that the user passes both namespaces and exclude patterns. In the case where both are set we will exclude references with unstripped names, even though we really wanted to exclude references based on their stripped names.
This only surfaces when:
- A repository uses reference namespaces.
- "transfer.hideRefs" is active.
- The namespaced references are packed into the "packed-refs" file.
None of our tests exercise this scenario, and thus we haven't ever hit it. While t5509 exercises both (1) and (2), it does not happen to hit (3). It is trivial to demonstrate the bug though by explicitly packing refs in the tests, and then we indeed surface the breakage.
Fix this bug by prefixing exclude patterns with the namespace in the generic layer. The newly introduced function will be used outside of "refs.c" in the next patch, so we add a declaration to "refs.h".
--- refs.c | 35 ++++++++++++++++++++++++++++---- refs.h | 9 ++++++++ t/t5509-fetch-push-namespaces.sh | 1 + 3 files changed, 41 insertions(+), 4 deletions(-)
refs.c +31 -4
@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out) +{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns) +return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +const char *find_descendant_ref (const char *dirname,const struct string_list *extras,const struct string_list *skip)
@@ -1634,11 +1647,19 @@ int refs_for_each_namespaced_ref(struct ref_store *refs,const char **exclude_patterns, each_ref_fn fn, void *cb_data) { - struct strbuf buf = STRBUF_INIT; + struct strvec namespaced_exclude_patterns = STRVEC_INIT; +struct strbuf prefix =STRBUF_INIT ;int ret; -strbuf_addf (&buf,"%srefs/" ,get_git_namespace ()); - ret =do_for_each_ref (refs, buf.buf, exclude_patterns, fn,0 ,0 , cb_data); -strbuf_release (&buf); + + exclude_patterns =get_namespaced_exclude_patterns (exclude_patterns, +get_git_namespace (), + &namespaced_exclude_patterns); + +strbuf_addf (&prefix,"%srefs/" ,get_git_namespace ()); + ret =do_for_each_ref (refs, prefix.buf, exclude_patterns, fn,0 ,0 , cb_data); + +strvec_clear (&namespaced_exclude_patterns); +strbuf_release (&prefix);return ret; }
@@ -1719,6 +1740,7 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,const char **exclude_patterns, each_ref_fn fn, void *cb_data) { + struct strvec namespaced_exclude_patterns = STRVEC_INIT;struct string_list prefixes =STRING_LIST_INIT_DUP ;struct string_list_item *prefix;struct strbuf buf =STRBUF_INIT ;
@@ -1730,6 +1752,10 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,strbuf_addstr (&buf, namespace); namespace_len = buf.len; + exclude_patterns =get_namespaced_exclude_patterns (exclude_patterns, + namespace, + &namespaced_exclude_patterns); +for_each_string_list_item (prefix, &prefixes) {strbuf_addstr (&buf, prefix->string); ret = refs_for_each_fullref_in(ref_store, buf.buf,
@@ -1739,6 +1765,7 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,strbuf_setlen (&buf, namespace_len); } +strvec_clear (&namespaced_exclude_patterns);string_list_clear (&prefixes,0 );strbuf_release (&buf);return ret;
refs.h +9 -0
@@ -859,6 +859,15 @@ int ref_is_hidden(const char *, const char *, const struct strvec *);*/ const char **hidden_refs_to_excludes (const struct strvec *hide_refs); +/* +* Prefix all exclude patterns with the namespace, if any. This is required +* because exclude patterns apply to the stripped reference name, not the full +* reference name with the namespace. +*/ +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out); +/* Is this a per-worktree ref living in the refs/ namespace? */ int is_per_worktree_ref (const char *refname);
t/t5509-fetch-push-namespaces.sh +1 -0
@@ -96,6 +96,7 @@ test_expect_success 'hide namespaced refs with transfer.hideRefs' ' ' test_expect_success 'check that transfer.hideRefs does not match unstripped refs' ' + git -C pushee pack-refs --all && GIT_NAMESPACE=namespace \ git -C pushee -c transfer.hideRefs=refs/namespaces/namespace/refs/tags \ ls-remote "ext::git %s ." >actual &&
Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 8 lines · Patrick Steinhardt
This only surfaces when:
- A repository uses reference namespaces.
- "transfer.hideRefs" is active.
- The namespaced references are packed into the "packed-refs" file.
Quoted 8 lines
None of our tests exercise this scenario, and thus we haven't ever hit it. While t5509 exercises both (1) and (2), it does not happen to hit (3). It is trivial to demonstrate the bug though by explicitly packing refs in the tests, and then we indeed surface the breakage.
Fix this bug by prefixing exclude patterns with the namespace in the generic layer. The newly introduced function will be used outside of "
refs.c" in the next patch, so we add a declaration to "refs.h".
Thanks for finding and fixing this bug!
Quoted 11 lines
refs.c +3
-0@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out)
refs.c const char **hidden_refs_to_excludes(const struct strvec *hide_refs) · line 1532
Quoted 10 lines
refs.c +10
-0+{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns) +return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +
Is it safe to concatenate each exclude pattern with the specified namespace? If I'm reading this correctly, I think we silently do the wrong thing for exclude patterns that start with '^'.
I guess we reject such patterns in the hidden_refs_to_excludes() function, but perhaps we wouldn't have to if this function stripped those prefixes for us when the caller does or doesn't specify exclude patterns with a '^'?
Thanks,
Taylor
Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 27 lines · Taylor Blau
Quoted 11 lines · Patrick Steinhardt
refs.c +3
-0@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out)refs.c const char **hidden_refs_to_excludes(const struct strvec *hide_refs) · line 1532
Quoted 10 lines
refs.c +10
-0+{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns) +return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +Is it safe to concatenate each exclude pattern with the specified namespace? If I'm reading this correctly, I think we silently do the wrong thing for exclude patterns that start with '^'.
Quoted 4 lines
I guess we reject such patterns in the
hidden_refs_to_excludes()function, but perhaps we wouldn't have to if this function stripped those prefixes for us when the caller does or doesn't specify exclude patterns with a '^'?
Yeah, as you mention, hidden_refs_to_excludes() drops excludes completely in case there's any pattern starting with '^' or '!'. So the current assumption should be safe because we don't use excludes in this scenario at all.
I also agree that we should eventually think about allowing '^'-scoped references. We can handle them correctly, but it requires a bit more thought wire that up. So I'd prefer to keep that out of this series, as it is basically a new feature.
Patrick
Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 28 lines · Patrick Steinhardt
Quoted 27 lines · Taylor Blau
Quoted 11 lines · Patrick Steinhardt
refs.c +3
-0@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out)refs.c const char **hidden_refs_to_excludes(const struct strvec *hide_refs) · line 1532
Quoted 10 lines
refs.c +10
-0+{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns) +return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +Is it safe to concatenate each exclude pattern with the specified namespace? If I'm reading this correctly, I think we silently do the wrong thing for exclude patterns that start with '^'.
Quoted 8 lines
Quoted 4 lines
I guess we reject such patterns in the
hidden_refs_to_excludes()function, but perhaps we wouldn't have to if this function stripped those prefixes for us when the caller does or doesn't specify exclude patterns with a '^'?Yeah, as you mention,
hidden_refs_to_excludes()drops excludes completely in case there's any pattern starting with '^' or '!'. So the current assumption should be safe because we don't use excludes in this
Right... but can't exclude_patterns be arbitrary here, as it is a parameter to the function which is exported via the *.h header file?
IOW, I don't think we can claim at all that we have passed the excluded patterns through hidden_refs_to_excludes() before calling get_namespaced_exclude_patterns().
Quoted 4 lines
I also agree that we should eventually think about allowing '^'-scoped references. We can handle them correctly, but it requires a bit more thought wire that up. So I'd prefer to keep that out of this series, as it is basically a new feature.
Yeah, I agree.
Thanks,
Taylor
Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 38 lines · Taylor Blau
Quoted 28 lines · Patrick Steinhardt
Quoted 27 lines · Taylor Blau
Quoted 11 lines · Patrick Steinhardt
refs.c +3
-0@@ -1517,6 +1517,19 @@ const char **hidden_refs_to_excludes(const struct strvec *hide_refs)return hide_refs->v; } +const char **get_namespaced_exclude_patterns (const char **exclude_patterns, +const char *namespace, +struct strvec *out)refs.c const char **hidden_refs_to_excludes(const struct strvec *hide_refs) · line 1532
Quoted 10 lines
refs.c +10
-0+{ +if (!namespace || !*namespace || !exclude_patterns || !*exclude_patterns) +return exclude_patterns; + +for (size_t i =0 ; exclude_patterns[i]; i++) +strvec_pushf (out,"%s%s" , namespace, exclude_patterns[i]); + +return out->v; +} +Is it safe to concatenate each exclude pattern with the specified namespace? If I'm reading this correctly, I think we silently do the wrong thing for exclude patterns that start with '^'.
Quoted 8 lines
Quoted 4 lines
I guess we reject such patterns in the
hidden_refs_to_excludes()function, but perhaps we wouldn't have to if this function stripped those prefixes for us when the caller does or doesn't specify exclude patterns with a '^'?Yeah, as you mention,
hidden_refs_to_excludes()drops excludes completely in case there's any pattern starting with '^' or '!'. So the current assumption should be safe because we don't use excludes in this
Quoted 6 lines
Right... but can't
exclude_patternsbe arbitrary here, as it is a parameter to the function which is exported via the *.h header file?IOW, I don't think we can claim at all that we have passed the excluded patterns through
hidden_refs_to_excludes()before callingget_namespaced_exclude_patterns().
I think the important thing to realize is that we're talking about two different things:
- We have exclude patterns. These are _patterns_ only and do not support '^' or '!'. These patterns are handled by the ref backend.
- We have hidden refs, which are a mechanism of our transport layer.
These _can_ support '^' or '!'.
To use hidden refs as exclude patterns they need to get translated to use the exclude pattern syntax, which does not support every feature that the hidden ref syntax does.
So every caller that uses exclude patterns must already make sure to filter things accordingly, and they must make sure to use the correct syntax for exclude patterns. And if they do, I think that the conversion to namespaced exclude patterns should be correct.
Or am I missing something?
Patrick
Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 2 lines · Patrick Steinhardt
I think the important thing to realize is that we're talking about two different things:
Wow, I'm sorry -- I completely misunderstood what was going on in this diff.
I have to say, that is quite embarrassing having written this feature only a little over a year ago. Sorry for the confusion, this patch LGTM.
Thanks,
Taylor
Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs
Quoted 9 lines · Taylor Blau
Quoted 2 lines · Patrick Steinhardt
I think the important thing to realize is that we're talking about two different things:
Wow, I'm sorry -- I completely misunderstood what was going on in this diff.
I have to say, that is quite embarrassing having written this feature only a little over a year ago. Sorry for the confusion, this patch LGTM.
No worries! If at all it points out that the patch message could've been clearer.
Patrick
PATCH v2 2/6 builtin/receive-pack: fix exclude patterns when announcing refs
In reply to Patrick SteinhardtIn write_head_info() we announce references to the remote client. We need to honor "transfer.hideRefs" here so that we do not announce any references that the client shouldn't be able to learn about. This is done via two separate mechanisms:
- We hand over exclude patterns to the reference backend. We can only honor "plain" exclude patterns here that do not have prefixes with special meaning such as "^" or "!". Filtering down the references is handled by hidden_refs_to_excludes().
- In show_ref_cb() we perform a second check against hidden refs. For one this is done such that we can handle those special prefixes. And second, handling exclude patterns in ref backends is optional, so we also have to handle "normal" patterns.
The special-meaning "^" prefix alters whether a hidden ref applies to the namespace-stripped reference name or the full name. So while we would usually call refs_for_each_namespaced_ref() to only get those references in the current namespace, we can't because we'd get the already-rewritten reference names. Instead, we are forced to use refs_for_each_fullref_in() and then manually strip away the namespace prefix such that we have access to both names.
But this also means that we do not get namespace handling for exclude patterns, which refs_for_each_namespaced_ref() brings for free. This results in a bug because we potentially end up hiding away references based on their namespaced name and not on the stripped name as we really should be doing.
Fix this by manually rewriting the exclude patterns to their namespaced variants.
--- builtin/receive-pack.c | 18 ++++++++++++++++-- t/t5509-fetch-push-namespaces.sh | 8 ++++++++ 2 files changed, 24 insertions(+), 2 deletions(-)
builtin/receive-pack.c +16 -2
@@ -339,12 +339,26 @@ static void show_one_alternate_ref(const struct object_id *oid,static void write_head_info (void ) {static struct oidset seen =OIDSET_INIT ; +struct strvec excludes_vector =STRVEC_INIT ; +const char **exclude_patterns; + +/* +* We need access to the reference names both with and without their +* namespace and thus cannot use `refs_for_each_namespaced_ref()`. We +* thus have to adapt exclude patterns to carry the namespace prefix +* ourselves. +*/ + exclude_patterns =get_namespaced_exclude_patterns ( +hidden_refs_to_excludes (&hidden_refs), +get_git_namespace (), &excludes_vector);refs_for_each_fullref_in (get_main_ref_store (the_repository),"" , -hidden_refs_to_excludes (&hidden_refs), - show_ref_cb, &seen); + exclude_patterns, show_ref_cb, &seen);for_each_alternate_ref (show_one_alternate_ref, &seen); +oidset_clear (&seen); +strvec_clear (&excludes_vector); +if (!sent_capabilities)show_ref ("capabilities^{}" ,null_oid ());
t/t5509-fetch-push-namespaces.sh +8 -0
@@ -124,6 +124,14 @@ test_expect_success 'try to update a ref that is not hidden' ' git -C original push pushee-namespaced main ' +test_expect_success 'git-receive-pack(1) with transfer.hideRefs does not match unstripped refs during advertisement' ' + git -C pushee update-ref refs/namespaces/namespace/refs/heads/foo/1 refs/namespaces/namespace/refs/heads/main && + git -C pushee pack-refs --all && + test_config -C pushee transfer.hideRefs refs/namespaces/namespace/refs/heads/foo && + GIT_TRACE_PACKET="$(pwd)/trace" git -C original push pushee-namespaced main && + test_grep refs/heads/foo/1 trace +' + test_expect_success 'try to update a hidden full ref' ' test_config -C pushee transfer.hideRefs "^refs/namespaces/namespace/refs/heads/main" && test_must_fail git -C original push pushee-namespaced main
Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
Re: [PATCH v2 2/6] builtin/receive-pack: fix exclude patterns when announcing refs
Quoted 10 lines · Patrick Steinhardt
builtin/receive-pack.c +2
-0@@ -339,12 +339,26 @@ static void show_one_alternate_ref(const struct object_id *oid,static void write_head_info (void ) {static struct oidset seen =OIDSET_INIT ; +struct strvec excludes_vector =STRVEC_INIT ; +const char **exclude_patterns;
builtin/receive-pack.c static void show_one_alternate_ref(const struct object_id *oid, · line 353
Quoted 10 lines
builtin/receive-pack.c +10
-0+ +/* +* We need access to the reference names both with and without their +* namespace and thus cannot use `refs_for_each_namespaced_ref()`. We +* thus have to adapt exclude patterns to carry the namespace prefix +* ourselves. +*/ + exclude_patterns =get_namespaced_exclude_patterns ( +hidden_refs_to_excludes (&hidden_refs), +get_git_namespace (), &excludes_vector);
OK, so here we use the result of calling hidden_refs_to_excludes() as the first argument to your new get_namespaced_exclude_patterns().
But I think that in this case when the caller specifies a pattern with '^', we still do not exclude any references in the backend, since hidden_refs_to_excludes() will return NULL when there is >1 pattern with '^' as the first character.
I don't think that this results in broken behavior, since the callback to the refs API will still be expected to filter out references that it doesn't want.
builtin/receive-pack.c static void show_one_alternate_ref(const struct object_id *oid, · line 357
Quoted 5 lines
builtin/receive-pack.c +1
-2refs_for_each_fullref_in (get_main_ref_store (the_repository),"" , -hidden_refs_to_excludes (&hidden_refs), - show_ref_cb, &seen); + exclude_patterns, show_ref_cb, &seen);for_each_alternate_ref (show_one_alternate_ref, &seen);
Thanks,
Taylor
PATCH v2 3/6 Makefile: stop listing test library objects twice
In reply to Patrick SteinhardtWhenever one adds another test library compilation unit one has to wire it up twice in the Makefile: once to append it to UNIT_TEST_OBJS, and once to append it to the UNIT_TEST_PROGS target. Ideally, we'd just reuse the UNIT_TEST_OBJS variable in the target so that we can avoid the duplication. But it also contains all the objects for our test programs, each of which contains a cmd_main(), and thus we cannot link them all into the target executable.
Refactor the code such that UNIT_TEST_OBJS does not contain the unit test program objects anymore, which we can instead manually append to the OBJECTS variable. Like this, the former variable now only contains objects for test libraries and can thus be reused.
--- Makefile | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-)
Makefile +2 -4
@@ -1356,7 +1356,6 @@ UNIT_TEST_PROGRAMS += t-strvec UNIT_TEST_PROGRAMS += t-trailer UNIT_TEST_PROGRAMS += t-urlmatch-normalization UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS)) -UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS)) UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-oid.o
@@ -2715,6 +2714,7 @@ OBJECTS += $(XDIFF_OBJS) OBJECTS += $(FUZZ_OBJS) OBJECTS += $(REFTABLE_OBJS) $(REFTABLE_TEST_OBJS) OBJECTS += $(UNIT_TEST_OBJS) +OBJECTS += $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS)) ifndef NO_CURL OBJECTS += http.o http-walker.o remote-curl.o
@@ -3852,9 +3852,7 @@ $(FUZZ_PROGRAMS): %: %.o oss-fuzz/dummy-cmd-main.o $(GITLIBS) GIT-LDFLAGS -Wl,--allow-multiple-definition \ $(filter %.o,$^) $(filter %.a,$^) $(LIBS) $(LIB_FUZZING_ENGINE) -$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o \ - $(UNIT_TEST_DIR)/test-lib.o \ - $(UNIT_TEST_DIR)/lib-oid.o \ +$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o $(UNIT_TEST_OBJS) \ $(GITLIBS) GIT-LDFLAGS $(call mkdir_p_parent_template) $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) \
Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
PATCH v2 4/6 t/unit-tests: introduce reftable library
In reply to Patrick SteinhardtWe have recently migrated all of the reftable unit tests that were part of the reftable library into our own unit testing framework. As part of that migration we have duplicated some of the functionality that was part of the reftable test framework into each of the migrated test suites. This was a sensible decision to not have all of the migrations dependent on each other, but now that the migration is done it makes sense to deduplicate the functionality again.
Introduce a new reftable test library that hosts some shared code and adapt tests to use it.
--- Makefile | 1 + t/unit-tests/lib-reftable.c | 93 ++++++++++++++++++++ t/unit-tests/lib-reftable.h | 20 +++++ t/unit-tests/t-reftable-merged.c | 87 +++---------------- t/unit-tests/t-reftable-readwrite.c | 130 +++++++++------------------- t/unit-tests/t-reftable-stack.c | 25 +++--- 6 files changed, 177 insertions(+), 179 deletions(-) create mode 100644 t/unit-tests/lib-reftable.c create mode 100644 t/unit-tests/lib-reftable.h
Makefile +1 -0
@@ -1358,6 +1358,7 @@ UNIT_TEST_PROGRAMS += t-urlmatch-normalization UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS)) UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-oid.o +UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-reftable.o # xdiff and reftable libs may in turn depend on what is in libgit.a GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) $(LIB_FILE)
t/unit-tests/lib-reftable.c new file +93 -0
93 lines not on this page · raw message
t/unit-tests/lib-reftable.h new file +20 -0
@@ -0,0 +1,20 @@ +#ifndef LIB_REFTABLE_H +#define LIB_REFTABLE_H + +#include "git-compat-util.h" +#include "strbuf.h" +#include "reftable/reftable-writer.h" + +void t_reftable_set_hash (uint8_t *p,int i,uint32_t id); + +struct reftable_writer *t_reftable_strbuf_writer (struct strbuf *buf, +struct reftable_write_options *opts); + +void t_reftable_write_to_buf (struct strbuf *buf, +struct reftable_ref_record *refs, +size_t nrecords, +struct reftable_log_record *logs, +size_t nlogs, +struct reftable_write_options *opts); + +#endif
t/unit-tests/t-reftable-merged.c +11 -76
129 lines not on this page · raw message
t/unit-tests/t-reftable-readwrite.c +40 -90
246 lines not on this page · raw message
t/unit-tests/t-reftable-stack.c +12 -13
@@ -7,17 +7,13 @@ license that can be found in the LICENSE file or at*/ #include "test-lib.h" +#include "lib-reftable.h" #include "reftable/merged.h" #include "reftable/reader.h" #include "reftable/reftable-error.h" #include "reftable/stack.h" #include <dirent.h> -static void set_test_hash (uint8_t *p,int i) -{ -memset (p, (uint8_t )i,hash_size (GIT_SHA1_FORMAT_ID )); -} -static void clear_dir (const char *dirname) {struct strbuf path =STRBUF_INIT ;
@@ -125,7 +121,7 @@ static void write_n_ref_tables(struct reftable_stack *st,strbuf_reset (&buf);strbuf_addf (&buf,"refs/heads/branch-%04" PRIuMAX, (uintmax_t )i); ref.refname = buf.buf; -set_test_hash (ref.value.val1, i); +t_reftable_set_hash (ref.value.val1, i,GIT_SHA1_FORMAT_ID ); err =reftable_stack_add (st, &write_test_ref, &ref);check (!err);
@@ -470,13 +466,13 @@ static void t_reftable_stack_add(void) refs[i].refname =xstrdup (buf); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; -set_test_hash (refs[i].value.val1, i); +t_reftable_set_hash (refs[i].value.val1, i,GIT_SHA1_FORMAT_ID ); logs[i].refname =xstrdup (buf); logs[i].update_index =N + i +1 ; logs[i].value_type =REFTABLE_LOG_UPDATE ; logs[i].value.update.email =xstrdup ("identity@invalid" ); -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i,GIT_SHA1_FORMAT_ID ); }for (i =0 ; i <N ; i++) {
@@ -562,14 +558,14 @@ static void t_reftable_stack_iterator(void) refs[i].refname =xstrfmt ("branch%02" PRIuMAX, (uintmax_t )i); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; -set_test_hash (refs[i].value.val1, i); +t_reftable_set_hash (refs[i].value.val1, i,GIT_SHA1_FORMAT_ID ); logs[i].refname =xstrfmt ("branch%02" PRIuMAX, (uintmax_t )i); logs[i].update_index = i +1 ; logs[i].value_type =REFTABLE_LOG_UPDATE ; logs[i].value.update.email =xstrdup ("johndoe@invalid" ); logs[i].value.update.message =xstrdup ("commit\n" ); -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i,GIT_SHA1_FORMAT_ID ); }for (i =0 ; i <N ; i++) {
@@ -704,7 +700,8 @@ static void t_reftable_stack_tombstone(void) refs[i].update_index = i +1 ;if (i %2 ==0 ) { refs[i].value_type =REFTABLE_REF_VAL1 ; -set_test_hash (refs[i].value.val1, i); +t_reftable_set_hash (refs[i].value.val1, i, +GIT_SHA1_FORMAT_ID ); } logs[i].refname =xstrdup (buf);
@@ -712,7 +709,8 @@ static void t_reftable_stack_tombstone(void) logs[i].update_index =42 ;if (i %2 ==0 ) { logs[i].value_type =REFTABLE_LOG_UPDATE ; -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i, +GIT_SHA1_FORMAT_ID ); logs[i].value.update.email =xstrdup ("identity@invalid" ); }
@@ -844,7 +842,8 @@ static void t_reflog_expire(void) logs[i].value_type =REFTABLE_LOG_UPDATE ; logs[i].value.update.time = i; logs[i].value.update.email =xstrdup ("identity@invalid" ); -set_test_hash (logs[i].value.update.new_hash, i); +t_reftable_set_hash (logs[i].value.update.new_hash, i, +GIT_SHA1_FORMAT_ID ); }for (i =1 ; i <=N ; i++) {
Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
PATCH v2 5/6 reftable/reader: make table iterator reseekable
In reply to Patrick SteinhardtIn 67ce50ba26 (Merge branch 'ps/reftable-reusable-iterator', 2024-05-30) we have refactored the interface of reftable iterators such that they can be reused in theory. This patch series only landed the required changes on the interface level, but didn't yet implement the actual logic to make iterators reusable.
As it turns out almost all of the infrastructure already does support re-seeking. The only exception is the table iterator, which does not reset its is_finished bit. Do so and add a couple of tests that verify that we can re-seek iterators.
--- Makefile | 1 + reftable/reader.c | 1 + t/unit-tests/t-reftable-merged.c | 76 +++++++++++++++++++++++++ t/unit-tests/t-reftable-reader.c | 96 ++++++++++++++++++++++++++++++++ 4 files changed, 174 insertions(+) create mode 100644 t/unit-tests/t-reftable-reader.c
Makefile +1 -0
@@ -1346,6 +1346,7 @@ UNIT_TEST_PROGRAMS += t-reftable-basics UNIT_TEST_PROGRAMS += t-reftable-block UNIT_TEST_PROGRAMS += t-reftable-merged UNIT_TEST_PROGRAMS += t-reftable-pq +UNIT_TEST_PROGRAMS += t-reftable-reader UNIT_TEST_PROGRAMS += t-reftable-readwrite UNIT_TEST_PROGRAMS += t-reftable-record UNIT_TEST_PROGRAMS += t-reftable-stack
reftable/reader.c +1 -0
@@ -328,6 +328,7 @@ static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ) ti->typ =block_reader_type (&ti->br); ti->block_off = off;block_iter_seek_start (&ti->bi, &ti->br); + ti->is_finished =0 ;return 0 ; }
t/unit-tests/t-reftable-merged.c +76 -0
88 lines not on this page · raw message
t/unit-tests/t-reftable-reader.c new file +96 -0
96 lines not on this page · raw message
Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
PATCH v2 6/6 refs/reftable: wire up support for exclude patterns
In reply to Patrick SteinhardtExclude patterns can be used by reference backends to skip over blocks of references that are uninteresting to the caller. Reference backends do not have to wire up support for them, and all callers are expected to behave as if the backend didn't support them. In fact, the only backend that supports exclude patterns right now is the "packed" backend.
Exclude patterns can be quite an important performance optimization in repositories that have loads of references. The patterns are set up in case "transfer.hideRefs" and friends are configured during a fetch, so handling these patterns becomes important once there are lots of hidden refs in a served repository.
Now that we have properly re-seekable reftable iterators we can also wire up support for these patterns in the "reftable" backend. Doing so is conceptually simple: once we hit a reference whose prefix matches the current exclude pattern we re-seek the iterator to the first reference that doesn't match the pattern anymore. This schema only works for trivial patterns that do not have any globbing characters in them, but this restriction also applies do the "packed" backend.
This makes t1419 work with the "reftable" backend with some slight modifications. Of course it also speeds up listing of references with hidden refs. The following benchmark prints one reference with 1 million hidden references:
Benchmark 1: HEAD~
Time (mean ± σ): 93.3 ms ± 2.1 ms [User: 90.3 ms, System: 2.5 ms]
Range (min … max): 89.8 ms … 97.2 ms 33 runs
Benchmark 2: HEAD
Time (mean ± σ): 4.2 ms ± 0.6 ms [User: 2.2 ms, System: 1.8 ms]
Range (min … max): 3.1 ms … 8.1 ms 765 runs
Summary
HEAD ran
22.15 ± 3.19 times faster than HEAD~
--- refs/reftable-backend.c | 133 +++++++++++++++++++++++++++++++++++++++- t/t1419-exclude-refs.sh | 49 ++++++++++++--- trace2.h | 1 + trace2/tr2_ctr.c | 5 ++ 4 files changed, 176 insertions(+), 12 deletions(-)
refs/reftable-backend.c +130 -3
@@ -21,6 +21,7 @@#include "../reftable/reftable-iterator.h" #include "../setup.h" #include "../strmap.h" +#include "../trace2.h" #include "parse.h" #include "refs-internal.h"
@@ -447,10 +448,81 @@ struct reftable_ref_iterator {const char *prefix;size_t prefix_len; +char **exclude_patterns; +size_t exclude_patterns_index; +size_t exclude_patterns_strlen;unsigned int flags;int err; }; +/* +* Handle exclude patterns. Returns either `1`, which tells the caller that the +* current reference shall not be shown. Or `0`, which indicates that it should +* be shown. +*/ +static int should_exclude_current_ref (struct reftable_ref_iterator *iter) +{ +while (iter->exclude_patterns[iter->exclude_patterns_index]) { +const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index]; +char *ref_after_pattern; +int cmp; + +/* +* Lazily cache the pattern length so that we don't have to +* recompute it every time this function is called. +*/ +if (!iter->exclude_patterns_strlen) + iter->exclude_patterns_strlen =strlen (pattern); + +/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches. +* +* Otherwise, if it's smaller, then we do not have a match and +* thus want to show the current reference. +*/ + cmp =strncmp (iter->ref.refname, pattern, + iter->exclude_patterns_strlen); +if (cmp >0 ) { + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +continue ; + } +if (cmp <0 ) +return 0 ; + +/* +* The reference shares a prefix with the exclude pattern and +* shall thus be omitted. We skip all references that match the +* pattern by seeking to the first reference after the block of +* matches. +* +* This is done by appending the highest possible character to +* the pattern. Consequently, all references that have the +* pattern as prefix and whose suffix starts with anything in +* the range [0x00, 0xfe] are skipped. And given that 0xff is a +* non-printable character that shouldn't ever be in a ref name, +* we'd not yield any such record, either. +* +* Note that the seeked-to reference may also be excluded. This +* is not handled here though, but the caller is expected to +* loop and re-verify the next reference for us. +*/ + ref_after_pattern =xstrfmt ("%s%c" , pattern,0xff ); + iter->err =reftable_iterator_seek_ref (&iter->iter, ref_after_pattern); + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +trace2_counter_add (TRACE2_COUNTER_ID_REFTABLE_RESEEKS ,1 ); + +free (ref_after_pattern); +return 1 ; + } + +return 0 ; +} +static int reftable_ref_iterator_advance (struct ref_iterator *ref_iterator) { struct reftable_ref_iterator *iter =
@@ -481,6 +553,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)break ; } +if (iter->exclude_patterns &&should_exclude_current_ref (iter)) +continue ; +if (iter->flags &DO_FOR_EACH_PER_WORKTREE_ONLY &&parse_worktree_ref (iter->ref.refname,NULL ,NULL ,NULL ) !=REF_WORKTREE_CURRENT )
@@ -570,6 +645,11 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) (struct reftable_ref_iterator *)ref_iterator;reftable_ref_record_release (&iter->ref);reftable_iterator_destroy (&iter->iter); +if (iter->exclude_patterns) { +for (size_t i =0 ; iter->exclude_patterns[i]; i++) +free (iter->exclude_patterns[i]); +free (iter->exclude_patterns); + }free (iter);return ITER_DONE ; }
@@ -580,9 +660,53 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .abort = reftable_ref_iterator_abort }; +static int qsort_strcmp (const void *va,const void *vb) +{ +const char *a = *(const char **)va; +const char *b = *(const char **)vb; +return strcmp (a, b); +} + +static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i]; +int has_glob =0 ; + +if (!exclude_pattern) +break ; + +for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + } +if (has_glob) +continue ; + +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =xstrdup (exclude_pattern); + } + +if (filtered_size) { +QSORT (filtered, filtered_size, qsort_strcmp); +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =NULL ; + } + +return filtered; +} +static struct reftable_ref_iterator *ref_iterator_for_stack (struct reftable_ref_store *refs,struct reftable_stack *stack,const char *prefix, +const char **exclude_patterns,int flags) {struct reftable_ref_iterator *iter;
@@ -595,6 +719,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ iter->base.oid = &iter->oid; iter->flags = flags; iter->refs = refs; + iter->exclude_patterns =filter_exclude_patterns (exclude_patterns); ret = refs->err;if (ret)
@@ -616,7 +741,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_static struct ref_iterator *reftable_be_iterator_begin (struct ref_store *ref_store,const char *prefix, - const char **exclude_patterns UNUSED, +const char **exclude_patterns,unsigned int flags) {struct reftable_ref_iterator *main_iter, *worktree_iter;
@@ -627,7 +752,8 @@ static struct ref_iterator *reftable_be_iterator_begin(struct ref_store *ref_sto required_flags |=REF_STORE_ODB ; refs =reftable_be_downcast (ref_store, required_flags,"ref_iterator_begin" ); - main_iter =ref_iterator_for_stack (refs, refs->main_stack, prefix, flags); + main_iter =ref_iterator_for_stack (refs, refs->main_stack, prefix, + exclude_patterns, flags);/* * The worktree stack is only set when we're in an actual worktree
@@ -641,7 +767,8 @@ static struct ref_iterator *reftable_be_iterator_begin(struct ref_store *ref_sto* Otherwise we merge both the common and the per-worktree refs into a * single iterator. */ - worktree_iter =ref_iterator_for_stack (refs, refs->worktree_stack, prefix, flags); + worktree_iter =ref_iterator_for_stack (refs, refs->worktree_stack, prefix, + exclude_patterns, flags);return merge_ref_iterator_begin (&worktree_iter->base, &main_iter->base, ref_iterator_select,NULL ); }
t/t1419-exclude-refs.sh +40 -9
73 lines not on this page · raw message
trace2.h +1 -0
@@ -554,6 +554,7 @@ enum trace2_counter_id {TRACE2_COUNTER_ID_TEST2 ,/* emits summary and thread events */ TRACE2_COUNTER_ID_PACKED_REFS_JUMPS ,/* counts number of jumps */ +TRACE2_COUNTER_ID_REFTABLE_RESEEKS ,/* counts number of re-seeks */ /* counts number of fsyncs */ TRACE2_COUNTER_ID_FSYNC_WRITEOUT_ONLY,
trace2/tr2_ctr.c +5 -0
@@ -31,6 +31,11 @@ static struct tr2_counter_metadata tr2_counter_metadata[TRACE2_NUMBER_OF_COUNTER .name = "jumps_made", .want_per_thread_events = 0, }, + [TRACE2_COUNTER_ID_REFTABLE_RESEEKS] = { + .category = "reftable", + .name = "reseeks_made", + .want_per_thread_events = 0, + }, [TRACE2_COUNTER_ID_FSYNC_WRITEOUT_ONLY] = { .category = "fsync", .name = "writeout-only",
Signature · 1 line
2.46.0.551.gc5ee8f2d1c.dirty
Re: [PATCH v2 6/6] refs/reftable: wire up support for exclude patterns
Quoted 9 lines · Patrick Steinhardt
This makes t1419 work with the "reftable" backend with some slight modifications. Of course it also speeds up listing of references with hidden refs. The following benchmark prints one reference with 1 million hidden references:
Benchmark 1: HEAD~
Time (mean ± σ): 93.3 ms ± 2.1 ms [User: 90.3 ms, System: 2.5 ms]
Range (min … max): 89.8 ms … 97.2 ms 33 runs
Quoted 7 lines
Benchmark 2: HEAD
Time (mean ± σ): 4.2 ms ± 0.6 ms [User: 2.2 ms, System: 1.8 ms]
Range (min … max): 3.1 ms … 8.1 ms 765 runsSummary
HEAD ran
22.15 ± 3.19 times faster than HEAD~
Very nice.
Quoted 8 lines
refs/reftable-backend.c +8
-0+/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches. +* +* Otherwise, if it's smaller, then we do not have a match and +* thus want to show the current reference.
refs/reftable-backend.c struct reftable_ref_iterator { · line 494
Quoted 10 lines
refs/reftable-backend.c +10
-0+*/ + cmp =strncmp (iter->ref.refname, pattern, + iter->exclude_patterns_strlen); +if (cmp >0 ) { + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +continue ; + } +if (cmp <0 ) +return 0 ;
Perhaps I am showing my ignorance for the reftable backend, but is it OK to call strncmp() against all patterns here?
In the packed-refs implementation which I worked on with Peff sometime last year, we rejected exclude patterns that contain special glob characters in them for exactly this reason.
The implementation that I'm referring to has a helpful comment that jogged my memory for what we were thinking at the time (see the function refs/packed-backend.c::populate_excluded_jump_list()).
Ugh, I just read the next hunk below, so ignore me here ;-).
Quoted 25 lines
refs/reftable-backend.c +25
-0+static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i]; +int has_glob =0 ; + +if (!exclude_pattern) +break ; + +for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + } +if (has_glob) +continue ; + +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =xstrdup (exclude_pattern);
refs/reftable-backend.c static struct ref_iterator_vtable reftable_ref_iterator_vtable = { · line 704
Quoted 10 lines
refs/reftable-backend.c +10
-0+ } + +if (filtered_size) { +QSORT (filtered, filtered_size, qsort_strcmp); +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =NULL ; + } + +return filtered; +}
Ohhh, here's where we filter out un-excludeable patterns. Ignore me :-).
One question I had reading this is why we don't filter these out on the fly in the iterator itself instead of allocating a separate array that we have to xstrdup() into and free later on.
We may be at the point of diminishing returns here, but I wonder if allocating this thing is more expensive than a few redundant strcmp()s and calls to is_glob_special(). I dunno.
Thanks,
Taylor
Re: [PATCH v2 6/6] refs/reftable: wire up support for exclude patterns
Quoted 27 lines · Taylor Blau
Quoted 8 lines · Patrick Steinhardt
refs/reftable-backend.c +8
-0+/* +* When the reference name is lexicographically bigger than the +* current exclude pattern we know that it won't ever match any +* of the following references, either. We thus advance to the +* next pattern and re-check whether it matches. +* +* Otherwise, if it's smaller, then we do not have a match and +* thus want to show the current reference. refs/reftable-backend.c struct reftable_ref_iterator { · line 494
Quoted 10 lines
refs/reftable-backend.c +10
-0+*/ + cmp =strncmp (iter->ref.refname, pattern, + iter->exclude_patterns_strlen); +if (cmp >0 ) { + iter->exclude_patterns_index++; + iter->exclude_patterns_strlen =0 ; +continue ; + } +if (cmp <0 ) +return 0 ;Perhaps I am showing my ignorance for the reftable backend, but is it OK to call
strncmp()against all patterns here?In the packed-refs implementation which I worked on with Peff sometime last year, we rejected exclude patterns that contain special glob characters in them for exactly this reason.
Quoted 5 lines
The implementation that I'm referring to has a helpful comment that jogged my memory for what we were thinking at the time (see the function refs/packed-backend.c::populate_excluded_jump_list()).
Ugh, I just read the next hunk below, so ignore me here ;-).
;)
I was also wondering whether we'd want to amend the generic parts of the refs interface to filter out globs. But it is entirely feasible that a backend can indeed filter out globs efficiently, even though none of the current ones can. So it kind of makes sense to keep things as-is and let the backends themselves decide what they can use.
Quoted 38 lines
Quoted 25 lines
refs/reftable-backend.c +25
-0+static char **filter_exclude_patterns (const char **exclude_patterns) +{ +size_t filtered_size =0 , filtered_alloc =0 ; +char **filtered =NULL ; + +if (!exclude_patterns) +return NULL ; + +for (size_t i =0 ; ; i++) { +const char *exclude_pattern = exclude_patterns[i]; +int has_glob =0 ; + +if (!exclude_pattern) +break ; + +for (const char *p = exclude_pattern; *p; p++) { + has_glob =is_glob_special (*p); +if (has_glob) +break ; + } +if (has_glob) +continue ; + +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =xstrdup (exclude_pattern);refs/reftable-backend.c static struct ref_iterator_vtable reftable_ref_iterator_vtable = { · line 704
Quoted 10 lines
refs/reftable-backend.c +10
-0+ } + +if (filtered_size) { +QSORT (filtered, filtered_size, qsort_strcmp); +ALLOC_GROW (filtered, filtered_size +1 , filtered_alloc); + filtered[filtered_size++] =NULL ; + } + +return filtered; +}Ohhh, here's where we filter out un-excludeable patterns. Ignore me :-).
Quoted 7 lines
One question I had reading this is why we don't filter these out on the fly in the iterator itself instead of allocating a separate array that we have to
xstrdup()into and free later on.We may be at the point of diminishing returns here, but I wonder if allocating this thing is more expensive than a few redundant strcmp()s and calls to
is_glob_special(). I dunno.
I think duplicating the array is the right thing to do anyway to not get weird lifetime issues with the exclude patterns. A caller may set up a ref iterator that they may end up using for longer than they keep alive the exlude patterns passed to the iterator. So by duplicating the array we might end up wasting a bit of memory, but we avoid such lifetime problems completely, which I think is a win to make the infrastructure less fragile.
Thanks for your review!
Patrick
Re: [PATCH v2 6/6] refs/reftable: wire up support for exclude patterns
Quoted 9 lines · Patrick Steinhardt
Quoted 1 line
Ugh, I just read the next hunk below, so ignore me here ;-).
;)
I was also wondering whether we'd want to amend the generic parts of the refs interface to filter out globs. But it is entirely feasible that a backend can indeed filter out globs efficiently, even though none of the current ones can. So it kind of makes sense to keep things as-is and let the backends themselves decide what they can use.
Yep, agreed.
Quoted 8 lines
Quoted 7 lines
One question I had reading this is why we don't filter these out on the fly in the iterator itself instead of allocating a separate array that we have to
xstrdup()into and free later on.We may be at the point of diminishing returns here, but I wonder if allocating this thing is more expensive than a few redundant strcmp()s and calls to
is_glob_special(). I dunno.
Quoted 7 lines
I think duplicating the array is the right thing to do anyway to not get weird lifetime issues with the exclude patterns. A caller may set up a ref iterator that they may end up using for longer than they keep alive the exlude patterns passed to the iterator. So by duplicating the array we might end up wasting a bit of memory, but we avoid such lifetime problems completely, which I think is a win to make the infrastructure less fragile.
OK, I trust your judgement here over my own as not having nearly the familiarity with reftables as you do.
Thanks,
Taylor
Patrick Steinhardt <[email protected]> writes:
Hello,
Quoted 153 lines
Hi,
this is the second version of my patch series that fixes preexisting bugs with exclude patterns and wires them up for the reftable backend.
Changes compared to v1:
- Some typo fixes in commit messages.
- Mention that the newly introduced function in patch 1 will be used in patch 2, which is why it's declared in "
refs.h".- Use
check()instead ofcheck_int(ret, ==, 0).- Sort exclude patterns lexicographically. This fixes a bug where we might not correctly skip over some refs when patterns are passed to the reftable backend in non-lexicographic order. Add a test for this.
Thanks!
Patrick
Patrick Steinhardt (6):
refs: properly apply exclude patterns to namespaced refs builtin/receive-pack: fix exclude patterns when announcing refs
Makefile: stop listing test library objects twice t/unit-tests: introduce reftable library reftable/reader: make table iterator reseekable refs/reftable: wire up support for exclude patternsMakefile | 8 +- builtin/receive-pack.c | 18 ++- refs.c | 35 +++++- refs.h | 9 ++ refs/reftable-backend.c | 133 ++++++++++++++++++++++- reftable/reader.c | 1 + t/t1419-exclude-refs.sh | 49 +++++++-- t/t5509-fetch-push-namespaces.sh | 9 ++ t/unit-tests/lib-reftable.c | 93 ++++++++++++++++ t/unit-tests/lib-reftable.h | 20 ++++ t/unit-tests/t-reftable-merged.c | 163 +++++++++++++++------------- t/unit-tests/t-reftable-reader.c | 96 ++++++++++++++++ t/unit-tests/t-reftable-readwrite.c | 130 +++++++--------------- t/unit-tests/t-reftable-stack.c | 25 ++--- trace2.h | 1 + trace2/tr2_ctr.c | 5 + 16 files changed, 594 insertions(+), 201 deletions(-) create mode 100644 t/unit-tests/lib-reftable.c create mode 100644 t/unit-tests/lib-reftable.h create mode 100644 t/unit-tests/t-reftable-reader.cRange-diff against v1:
1:8d347bc5599! 1:7497166422erefs: properly apply exclude patterns to namespaced refs
@@ Commit message
to the non-stripped ones that still have the namespace prefix. In fact, the "transfer.hideRefs" machinery does the former and applies to the stripped reference by default, but rules can have "^" prefixed to switch
- this behaviour to iinstead match against the rull reference name.
+ this behaviour to instead match against the full reference name.Namespaces are exclusively handled at the generic "refs" layer, the respective backends have no clue that such a thing even exists. This
@@ Commit message
refs in the tests, and then we indeed surface the breakage.Fix this bug by prefixing exclude patterns with the namespace in the
- generic layer.
+ generic layer. The newly introduced function will be used outside of
+ "refs.c" in the next patch, so we add a declaration to "refs.h".Signed-off-by Patrick Steinhardt <[email protected]>2: 0317a5a7ede = 2: 3dc6ae936c8 builtin/receive-pack: fix exclude patterns when announcing refs 3: 503c44e6cab = 3: 4ba503520e6 Makefile: stop listing test library objects twice 4: 3df4040dd3c = 4: 6747076420f t/unit-tests: introduce reftable library 5: a281f936a2b ! 5: 3278cdf92fe reftable/reader: make table iterator reseekable @@ t/unit-tests/t-reftable-reader.c (new) + block_source_from_strbuf(&source, &buf); + + ret = reftable_reader_new(&reader, &source, "name"); -+ check_int(ret, ==, 0); ++ check(!ret); + + reftable_reader_init_ref_iterator(reader, &it); + ret = reftable_iterator_seek_ref(&it, ""); -+ check_int(ret, ==, 0); ++ check(!ret); + ret = reftable_iterator_next_ref(&it, &ref); -+ check_int(ret, ==, 0); ++ check(!ret); + -+ ret = reftable_ref_record_equal(&ref, &records[0], 20); ++ ret = reftable_ref_record_equal(&ref, &records[0], GIT_SHA1_RAWSZ); + check_int(ret, ==, 1); + + ret = reftable_iterator_next_ref(&it, &ref); @@ t/unit-tests/t-reftable-reader.c (new) + block_source_from_strbuf(&source, &buf); + + ret = reftable_reader_new(&reader, &source, "name"); -+ check_int(ret, ==, 0); ++ check(!ret); + + reftable_reader_init_ref_iterator(reader, &it); + + for (size_t i = 0; i < 5; i++) { + ret = reftable_iterator_seek_ref(&it, ""); -+ check_int(ret, ==, 0); ++ check(!ret); + ret = reftable_iterator_next_ref(&it, &ref); -+ check_int(ret, ==, 0); ++ check(!ret); + + ret = reftable_ref_record_equal(&ref, &records[0], GIT_SHA1_RAWSZ); + check_int(ret, ==, 1); 6: f3922b81db6 ! 6: 050f4906393 refs/reftable: wire up support for exclude patterns @@ refs/reftable-backend.c: static struct ref_iterator_vtable reftable_ref_iterator .abort = reftable_ref_iterator_abort }; ++static int qsort_strcmp(const void *va, const void *vb) ++{ ++ const char *a = *(const char **)va; ++ const char *b = *(const char **)vb; ++ return strcmp(a, b); ++} ++ +static char **filter_exclude_patterns(const char **exclude_patterns) +{ + size_t filtered_size = 0, filtered_alloc = 0; @@ refs/reftable-backend.c: static struct ref_iterator_vtable reftable_ref_iterator + } + + if (filtered_size) { ++ QSORT(filtered, filtered_size, qsort_strcmp); + ALLOC_GROW(filtered, filtered_size + 1, filtered_alloc); + filtered[filtered_size++] = NULL; + } @@ t/t1419-exclude-refs.sh: test_expect_success 'several overlapping excluded regio + assert_jumps 3 perf;; + *) + BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";; ++ esac ++' ++ ++test_expect_success 'unordered excludes' ' ++ for_each_ref__exclude refs/heads \ ++ refs/heads/foo refs/heads/baz >actual 2>perf && ++ for_each_ref refs/heads/bar refs/heads/quux >expect && ++ ++ test_cmp expect actual && ++ case "$GIT_DEFAULT_REF_FORMAT" in
Quoted 9 lines
++ files)
++ assert_jumps 1 perf;;
++ reftable)
++ assert_jumps 2 perf;;
++ *)
++ BUG "unhandled ref format $GIT_DEFAULT_REF_FORMAT";;
+ esac
'The range diff here looks good based on my earlier review. Thanks