Skip to contentSkip to conversation

refs/reftable: wire up exclude patterns

PATCH Superseded Patrick Steinhardt 3 participants 36 messages Sep 9, 2024 – Sep 17, 2024 Kbuild

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index ceb72d4bd74..b3a367ea12c 100644
@@ -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
index f8b919a1388..3f774e96d18 100644
@@ -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
index 05090feaf92..98e8352b6cc 100755
@@ -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
#4 lore raw

PATCH 2/6 builtin/receive-pack: fix exclude patterns when announcing refs

In reply to Patrick Steinhardt

In 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
index 3f35140e489..478c62ca836 100644
@@ -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
index 98e8352b6cc..f029ae0d286 100755
@@ -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
#6 lore raw

PATCH 3/6 Makefile: stop listing test library objects twice

In reply to Patrick Steinhardt

Whenever 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
index bdea061971a..4ed5f1f50a8 100644
@@ -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
#7 lore raw

PATCH 4/6 t/unit-tests: introduce reftable library

In reply to Patrick Steinhardt

We 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
index 4ed5f1f50a8..9460a80d0dd 100644
@@ -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
new file mode 100644
index 00000000000..d1154190847
@@ -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
index d62a9c1bed5..65e513d5ec8 100644
@@ -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
#8 lore raw

PATCH 5/6 reftable/reader: make table iterator reseekable

In reply to Patrick Steinhardt

In 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
index 9460a80d0dd..4039e355b09 100644
@@ -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
index f8770990876..6494ce2e327 100644
@@ -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
#12 lore raw

PATCH 6/6 refs/reftable: wire up support for exclude patterns

In reply to Patrick Steinhardt

Exclude 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
index 1c4b19e737f..5c241097a4e 100644
@@ -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
index 13595744190..8c7b69a9b34 100755
@@ -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
index 19e04bf040f..901f39253a6 100644
@@ -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
index d3a33715c14..036b643578b 100644
@@ -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
#2 lore raw

Re: [PATCH 1/6] refs: properly apply exclude patterns to namespaced refs

In reply to Patrick Steinhardt
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/$namespace prefix, 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() 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.

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.

---
 refs.c                           | 35 ++++++++++++++++++++++++++++----
 refs.h                           |  9 ++++++++
 t/t5509-fetch-push-namespaces.sh |  1 +
 3 files changed, 41 insertions(+), 4 deletions(-)
refs.c +0 -0
index ceb72d4bd74..b3a367ea12c 100644

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
index f8b919a1388..3f774e96d18 100644
@@ -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?

#5 lore raw

Re: [PATCH 2/6] builtin/receive-pack: fix exclude patterns when announcing refs

In reply to Patrick Steinhardt

Patrick Steinhardt <[email protected]> writes:

[snip]

Quoted 11 lines
builtin/receive-pack.c +3 -0
index 3f35140e489..478c62ca836 100644
@@ -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]

#9 lore raw

Re: [PATCH 5/6] reftable/reader: make table iterator reseekable

In reply to Patrick Steinhardt

Patrick Steinhardt <[email protected]> writes:

[snip]

Quoted 60 lines
t/unit-tests/t-reftable-merged.c +52 -0
index b8c92fdb365..19e54bdfb8b 100644
@@ -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
new file mode 100644
index 00000000000..7a46580b6f1
@@ -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 do
check(reftable_ref_record_equal(...)) or even
!check(reftable_iterator_seek_ref(...)) ?

[snip]

#13 lore raw

Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns

In reply to Patrick Steinhardt

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 runs

Summary
HEAD ran
22.15 ± 3.19 times faster than HEAD~

Nice.

Quoted 45 lines
---
 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
index 1c4b19e737f..5c241097a4e 100644
@@ -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]

#16 lore raw
In reply to Patrick Steinhardt
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

#3 lore raw

Re: [PATCH 1/6] refs: properly apply exclude patterns to namespaced refs

In reply to karthik nayak
Quoted 25 lines · karthik nayak
Quoted 7 lines · Patrick Steinhardt

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.

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.

Quoted 4 lines

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.

Yup.

Quoted 8 lines
Quoted 8 lines
refs.c +0 -0
index ceb72d4bd74..b3a367ea12c 100644
@@ -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 !*namespace be possible?

It's the default value of get_git_namespace().

Quoted 8 lines
Quoted 8 lines
refs.h +0 -0
index f8b919a1388..3f774e96d18 100644
@@ -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

#10 lore raw

Re: [PATCH 5/6] reftable/reader: make table iterator reseekable

In reply to karthik nayak
Quoted 35 lines · karthik nayak
Quoted 34 lines · Patrick Steinhardt
t/unit-tests/t-reftable-reader.c new file +28 -0
new file mode 100644
index 00000000000..7a46580b6f1
@@ -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

#14 lore raw

Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns

In reply to karthik nayak
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

#17 lore raw
In reply to karthik nayak
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

#18 lore raw

v2 cover refs/reftable: wire up exclude patterns

In reply to Patrick Steinhardt

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 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
#19 lore raw

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
index ceb72d4bd74..b3a367ea12c 100644
@@ -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
index f8b919a1388..3f774e96d18 100644
@@ -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
index 05090feaf92..98e8352b6cc 100755
@@ -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
#26 lore raw

PATCH v2 2/6 builtin/receive-pack: fix exclude patterns when announcing refs

In reply to Patrick Steinhardt

In 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
index 3f35140e489..478c62ca836 100644
@@ -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
index 98e8352b6cc..f029ae0d286 100755
@@ -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
#28 lore raw

PATCH v2 3/6 Makefile: stop listing test library objects twice

In reply to Patrick Steinhardt

Whenever 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
index bdea061971a..4ed5f1f50a8 100644
@@ -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
#29 lore raw

PATCH v2 4/6 t/unit-tests: introduce reftable library

In reply to Patrick Steinhardt

We 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
index 4ed5f1f50a8..9460a80d0dd 100644
@@ -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
new file mode 100644
index 00000000000..d1154190847
@@ -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
index d62a9c1bed5..65e513d5ec8 100644
@@ -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
#30 lore raw

PATCH v2 5/6 reftable/reader: make table iterator reseekable

In reply to Patrick Steinhardt

In 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
index 9460a80d0dd..4039e355b09 100644
@@ -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
index f8770990876..6494ce2e327 100644
@@ -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
#31 lore raw

PATCH v2 6/6 refs/reftable: wire up support for exclude patterns

In reply to Patrick Steinhardt

Exclude 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
index 1c4b19e737f..3e63833ce41 100644
@@ -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
index 19e04bf040f..901f39253a6 100644
@@ -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
index d3a33715c14..036b643578b 100644
@@ -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
#20 lore raw

Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs

In reply to Patrick Steinhardt
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
index ceb72d4bd74..b3a367ea12c 100644
@@ -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

#27 lore raw

Re: [PATCH v2 2/6] builtin/receive-pack: fix exclude patterns when announcing refs

In reply to Patrick Steinhardt
Quoted 10 lines · Patrick Steinhardt
builtin/receive-pack.c +2 -0
index 3f35140e489..478c62ca836 100644
@@ -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 -2
 	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);

Thanks,
Taylor

#32 lore raw

Re: [PATCH v2 6/6] refs/reftable: wire up support for exclude patterns

In reply to Patrick Steinhardt
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 runs

Summary
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

#21 lore raw

Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs

In reply to Taylor Blau
Quoted 27 lines · Taylor Blau
Quoted 11 lines · Patrick Steinhardt
refs.c +3 -0
index ceb72d4bd74..b3a367ea12c 100644
@@ -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

#22 lore raw

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
index ceb72d4bd74..b3a367ea12c 100644
@@ -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

#33 lore raw

Re: [PATCH v2 6/6] refs/reftable: wire up support for exclude patterns

In reply to Taylor Blau
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

#23 lore raw

Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs

In reply to Taylor Blau
Quoted 38 lines · Taylor Blau
Quoted 28 lines · Patrick Steinhardt
Quoted 27 lines · Taylor Blau
Quoted 11 lines · Patrick Steinhardt
refs.c +3 -0
index ceb72d4bd74..b3a367ea12c 100644
@@ -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_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().

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

#24 lore raw

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

#34 lore raw

Re: [PATCH v2 6/6] refs/reftable: wire up support for exclude patterns

In reply to Patrick Steinhardt
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

#25 lore raw

Re: [PATCH v2 1/6] refs: properly apply exclude patterns to namespaced refs

In reply to Taylor Blau
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

#11 lore raw

Re: [PATCH 5/6] reftable/reader: make table iterator reseekable

In reply to Patrick Steinhardt
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
new file mode 100644
index 00000000000..7a46580b6f1
@@ -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 use check(!...) because it is important that the returnd error code is positive.

Perfect!

Quoted 1 line

Patrick

Karthik

#15 lore raw

Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns

In reply to Patrick Steinhardt
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 that 0xff is 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.

#35 lore raw
In reply to Patrick Steinhardt

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 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
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