Git Mailing List Archive mirror
 help / color / mirror / Atom feed
From: "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>
To: Patrick Steinhardt <ps@pks.im>
Cc: git@vger.kernel.org
Subject: Re: [PATCH 2/2] receive-pack: use advertised reference tips to inform connectivity check
Date: Fri, 28 Oct 2022 17:01:58 +0200	[thread overview]
Message-ID: <221028.867d0k7yny.gmgdl@evledraar.gmail.com> (raw)
In-Reply-To: <006e89f384be1227b922fb6fdc8755ae84cac587.1666967670.git.ps@pks.im>


On Fri, Oct 28 2022, Patrick Steinhardt wrote:

> When serving a push, git-receive-pack(1) needs to verify that the
> packfile sent by the client contains all objects that are required by
> the updated references. This connectivity check works by marking all
> preexisting references as uninteresting and using the new reference tips
> as starting point for a graph walk.
>
> This strategy has the major downside that it will not require any object
> to be sent by the client that is reachable by any of the repositories'
> references. While that sounds like it would be indeed what we are after
> with the connectivity check, it is arguably not. The administrator that
> manages the server-side Git repository may have configured certain refs
> to be hidden during the reference advertisement via `transfer.hideRefs`
> or `receivepack.hideRefs`. Whatever the reason, the result is that the
> client shouldn't expect that any of those hidden references exists on
> the remote side, and neither should they assume any of the pointed-to
> objects to exist except if referenced by any visible reference. But
> because we treat _all_ local refs as uninteresting in the connectivity
> check, a client is free to send a packfile that references objects that
> are only reachable via a hidden reference on the server-side, and we
> will gladly accept it.
>
> Besides the correctness issue there is also a performance issue. Git
> forges tend to do internal bookkeeping to keep alive sets of objects for
> internal use or make them easy to find via certain references. These
> references are typically hidden away from the user so that they are
> neither advertised nor writeable. At GitLab, we have one particular
> repository that contains a total of 7 million references, of which 6.8
> million are indeed internal references. With the current connectivity
> check we are forced to load all these references in order to mark them
> as uninteresting, and this alone takes around 15 seconds to compute.
>
> We can fix both of these issues by changing the logic for stateful
> invocations of git-receive-pack(1) where the reference advertisement and
> packfile negotiation are served by the same process. Instead of marking
> all preexisting references as unreachable, we will only mark those that
> we have announced to the client.
>
> Besides the stated fix to correctness this also provides a huge boost to
> performance in the repository mentioned above. Pushing a new commit into
> this repo with `transfer.hideRefs` set up to hide 6.8 million of 7 refs
> as it is configured in Gitaly leads to an almost 7.5-fold speedup:

Really well explained.

>     Benchmark 1: main
>       Time (mean ± σ):     29.902 s ±  0.105 s    [User: 29.176 s, System: 1.052 s]
>       Range (min … max):   29.781 s … 29.969 s    3 runs
>
>     Benchmark 2: pks-connectivity-check-hide-refs
>       Time (mean ± σ):      4.033 s ±  0.088 s    [User: 4.071 s, System: 0.374 s]
>       Range (min … max):    3.953 s …  4.128 s    3 runs
>
>     Summary
>       'pks-connectivity-check-hide-refs' ran
>         7.42 ± 0.16 times faster than 'main'

And impressive, thanks!

> Unfortunately, this change comes with a performance hit when refs are
> not hidden. Executed in the same repository:
>
>     Benchmark 1: main
>       Time (mean ± σ):     45.780 s ±  0.507 s    [User: 46.908 s, System: 4.838 s]
>       Range (min … max):   45.453 s … 46.364 s    3 runs
>
>     Benchmark 2: pks-connectivity-check-hide-refs
>       Time (mean ± σ):     49.886 s ±  0.282 s    [User: 51.168 s, System: 5.015 s]
>       Range (min … max):   49.589 s … 50.149 s    3 runs
>
>     Summary
>       'main' ran
>         1.09 ± 0.01 times faster than 'pks-connectivity-check-hide-refs'
>
> This is probably caused by the overhead of reachable tips being passed
> in via git-rev-list(1)'s standard input, which seems to be slower than
> reading the references from disk.
>
> It is debatable what to do about this. If this were only about improving
> performance then it would be trivial to make the new logic depend on
> whether or not `transfer.hideRefs` has been configured in the repo. But
> as explained this is also about correctness, even though this can be
> considered an edge case. Furthermore, this slowdown is really only
> noticeable in outliers like the above repository with an unreasonable
> amount of refs. The same benchmark in linux-stable.git with about
> 4500 references shows no measurable difference:

Do we have a test that would start failing if we changed the behavior?
Perhaps such a test is peeking too much behind the curtain, but if it's
easy come up with one I think it would be most welcome to have it
alongside this.  to have exposes

> -static void write_head_info(void)
> +static void write_head_info(struct oidset *announced_objects)
>  {
> -	static struct oidset seen = OIDSET_INIT;
> -
> -	for_each_ref(show_ref_cb, &seen);
> -	for_each_alternate_ref(show_one_alternate_ref, &seen);
> -	oidset_clear(&seen);
> +	for_each_ref(show_ref_cb, announced_objects);
> +	for_each_alternate_ref(show_one_alternate_ref, announced_objects);
>  	if (!sent_capabilities)
>  		show_ref("capabilities^{}", null_oid());

Nit: The variable rename stands out slightly,
i.e. s/&seen/announced_objects/ not s/&seen/seen/, especially as:

>  static void execute_commands(struct command *commands,
>  			     const char *unpacker_error,
>  			     struct shallow_info *si,
> -			     const struct string_list *push_options)
> +			     const struct string_list *push_options,
> +			     struct oidset *announced_oids)

Here we have the same variable, but now it's *_oids, not *objects.

> +	if (oidset_size(announced_oids) != 0) {

Nit as before: The "!= 0" can go here.

> @@ -2462,6 +2473,7 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
>  {
>  	int advertise_refs = 0;
>  	struct command *commands;
> +	struct oidset announced_oids = OIDSET_INIT;
>  	struct oid_array shallow = OID_ARRAY_INIT;
>  	struct oid_array ref = OID_ARRAY_INIT;
>  	struct shallow_info si;
> @@ -2524,7 +2536,7 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
>  	}
>  
>  	if (advertise_refs || !stateless_rpc) {
> -		write_head_info();
> +		write_head_info(&announced_oids);
>  	}
>  	if (advertise_refs)
>  		return 0;

This introduces a memory leak to the function., We probably have other
ones in code it calls, but from a quick eyeballing not in the function
itself.

Squashing in / combining it with this should do it, as it never returns
non-zero (except for calling die()):
	
	diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
	index 44bcea3a5b3..8d5c2fbef1c 100644
	--- a/builtin/receive-pack.c
	+++ b/builtin/receive-pack.c
	@@ -2527,7 +2527,7 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
	 		write_head_info();
	 	}
	 	if (advertise_refs)
	-		return 0;
	+		goto cleanup;
	 
	 	packet_reader_init(&reader, 0, NULL, 0,
	 			   PACKET_READ_CHOMP_NEWLINE |
	@@ -2587,6 +2587,7 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
	 			update_server_info(0);
	 		clear_shallow_info(&si);
	 	}
	+cleanup:
	 	if (use_sideband)
	 		packet_flush(1);
	 	oid_array_clear(&shallow);

> @@ -2591,6 +2603,7 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
>  		packet_flush(1);
>  	oid_array_clear(&shallow);
>  	oid_array_clear(&ref);
> +	oidset_clear(&announced_oids);
>  	free((void *)push_cert_nonce);
>  	return 0;
>  }

We'll then properly reach this new oidset_clear()> The oid_array_clear()
are all for variables we're populating after we're past htat "if
(advertise_refs)".

I think if you're re-rolling this sqashing 1/2 and 2/2 together would be
an improvement. The 1/2 is tiny, and it's an API that's not used until
this 1/2. I found myself going back & forth more than helped in
reviewing this.

Ggoing back a bit this:

> +static const struct object_id *iterate_announced_oids(void *cb_data)
> +{
> +	struct oidset_iter *iter = cb_data;
> +	return oidset_iter_next(iter);
> +}
> +

Is just used as (from 1/2):

> +	if (opt->reachable_oids_fn) {
> +		const struct object_id *reachable_oid;
> +		while ((reachable_oid = opt->reachable_oids_fn(opt->reachable_oids_data)) != NULL)
> +			if (fprintf(rev_list_in, "^%s\n", oid_to_hex(reachable_oid)) < 0)
> +				break;
> +	}

After doing above:

> +	if (oidset_size(announced_oids) != 0) {
> +		oidset_iter_init(announced_oids, &announced_oids_iter);
> +		opt.reachable_oids_fn = iterate_announced_oids;
> +		opt.reachable_oids_data = &announced_oids_iter;
> +	}

But I don't see the reason for the indirection, but maybe I'm missing
something obvious.

Why not just pass the oidset itself and have connected.c iterate through
it, rather than going thorugh this callback / data indirection?


  reply	other threads:[~2022-10-28 15:31 UTC|newest]

Thread overview: 88+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-10-28 14:42 [PATCH 0/2] receive-pack: use advertised reference tips to inform connectivity check Patrick Steinhardt
2022-10-28 14:42 ` [PATCH 1/2] connected: allow supplying different view of reachable objects Patrick Steinhardt
2022-10-28 14:54   ` Ævar Arnfjörð Bjarmason
2022-10-28 18:12   ` Junio C Hamano
2022-10-30 18:49     ` Taylor Blau
2022-10-31 13:10     ` Patrick Steinhardt
2022-11-01  1:16       ` Taylor Blau
2022-10-28 14:42 ` [PATCH 2/2] receive-pack: use advertised reference tips to inform connectivity check Patrick Steinhardt
2022-10-28 15:01   ` Ævar Arnfjörð Bjarmason [this message]
2022-10-31 14:21     ` Patrick Steinhardt
2022-10-31 15:36       ` Ævar Arnfjörð Bjarmason
2022-10-30 19:09   ` Taylor Blau
2022-10-31 14:45     ` Patrick Steinhardt
2022-11-01  1:28       ` Taylor Blau
2022-11-01  7:20         ` Patrick Steinhardt
2022-11-01 11:53           ` Patrick Steinhardt
2022-11-02  1:05             ` Taylor Blau
2022-11-01  8:28       ` Jeff King
2022-10-28 16:40 ` [PATCH 0/2] " Junio C Hamano
2022-11-01  1:30 ` Taylor Blau
2022-11-01  9:00 ` Jeff King
2022-11-01 11:49   ` Patrick Steinhardt
2022-11-03 14:37 ` [PATCH v2 0/3] receive-pack: only use visible refs for " Patrick Steinhardt
2022-11-03 14:37   ` [PATCH v2 1/3] refs: get rid of global list of hidden refs Patrick Steinhardt
2022-11-03 14:37   ` [PATCH v2 2/3] revision: add new parameter to specify all visible refs Patrick Steinhardt
2022-11-05 12:46     ` Jeff King
2022-11-07  8:20       ` Patrick Steinhardt
2022-11-08 14:32         ` Jeff King
2022-11-05 12:55     ` Jeff King
2022-11-03 14:37   ` [PATCH v2 3/3] receive-pack: only use visible refs for connectivity check Patrick Steinhardt
2022-11-05  0:40   ` [PATCH v2 0/3] " Taylor Blau
2022-11-05 12:55     ` Jeff King
2022-11-05 12:52   ` Jeff King
2022-11-07 12:16 ` [PATCH v3 0/6] " Patrick Steinhardt
2022-11-07 12:16   ` [PATCH v3 1/6] refs: get rid of global list of hidden refs Patrick Steinhardt
2022-11-07 12:16   ` [PATCH v3 2/6] revision: move together exclusion-related functions Patrick Steinhardt
2022-11-07 12:16   ` [PATCH v3 3/6] revision: introduce struct to handle exclusions Patrick Steinhardt
2022-11-07 12:51     ` Ævar Arnfjörð Bjarmason
2022-11-08  9:11       ` Patrick Steinhardt
2022-11-07 12:16   ` [PATCH v3 4/6] revision: add new parameter to exclude hidden refs Patrick Steinhardt
2022-11-07 13:34     ` Ævar Arnfjörð Bjarmason
2022-11-07 17:07       ` Ævar Arnfjörð Bjarmason
2022-11-08  9:48         ` Patrick Steinhardt
2022-11-08  9:22       ` Patrick Steinhardt
2022-11-08  0:57     ` Taylor Blau
2022-11-08  8:16       ` Patrick Steinhardt
2022-11-08 14:42         ` Jeff King
2022-11-07 12:16   ` [PATCH v3 5/6] revparse: add `--exclude-hidden=` option Patrick Steinhardt
2022-11-08 14:44     ` Jeff King
2022-11-07 12:16   ` [PATCH v3 6/6] receive-pack: only use visible refs for connectivity check Patrick Steinhardt
2022-11-08  0:59   ` [PATCH v3 0/6] " Taylor Blau
2022-11-08 10:03 ` [PATCH v4 " Patrick Steinhardt
2022-11-08 10:03   ` [PATCH v4 1/6] refs: get rid of global list of hidden refs Patrick Steinhardt
2022-11-08 13:36     ` Ævar Arnfjörð Bjarmason
2022-11-08 14:49       ` Patrick Steinhardt
2022-11-08 14:51     ` Jeff King
2022-11-08 10:03   ` [PATCH v4 2/6] revision: move together exclusion-related functions Patrick Steinhardt
2022-11-08 10:03   ` [PATCH v4 3/6] revision: introduce struct to handle exclusions Patrick Steinhardt
2022-11-08 10:03   ` [PATCH v4 4/6] revision: add new parameter to exclude hidden refs Patrick Steinhardt
2022-11-08 15:07     ` Jeff King
2022-11-08 21:13       ` Taylor Blau
2022-11-11  5:48       ` Patrick Steinhardt
2022-11-08 10:03   ` [PATCH v4 5/6] rev-parse: add `--exclude-hidden=` option Patrick Steinhardt
2022-11-08 10:04   ` [PATCH v4 6/6] receive-pack: only use visible refs for connectivity check Patrick Steinhardt
2022-11-11  6:49 ` [PATCH v5 0/7] " Patrick Steinhardt
2022-11-11  6:49   ` [PATCH v5 1/7] refs: fix memory leak when parsing hideRefs config Patrick Steinhardt
2022-11-11  6:49   ` [PATCH v5 2/7] refs: get rid of global list of hidden refs Patrick Steinhardt
2022-11-11  6:50   ` [PATCH v5 3/7] revision: move together exclusion-related functions Patrick Steinhardt
2022-11-11  6:50   ` [PATCH v5 4/7] revision: introduce struct to handle exclusions Patrick Steinhardt
2022-11-11  6:50   ` [PATCH v5 5/7] revision: add new parameter to exclude hidden refs Patrick Steinhardt
2022-11-11  6:50   ` [PATCH v5 6/7] rev-parse: add `--exclude-hidden=` option Patrick Steinhardt
2022-11-11  6:50   ` [PATCH v5 7/7] receive-pack: only use visible refs for connectivity check Patrick Steinhardt
2022-11-11 22:18   ` [PATCH v5 0/7] " Taylor Blau
2022-11-15 17:26     ` Jeff King
2022-11-16 21:22       ` Taylor Blau
2022-11-16 22:04         ` Jeff King
2022-11-16 22:33           ` Taylor Blau
2022-11-17  5:45             ` Patrick Steinhardt
2022-11-17  5:46 ` [PATCH v6 " Patrick Steinhardt
2022-11-17  5:46   ` [PATCH v6 1/7] refs: fix memory leak when parsing hideRefs config Patrick Steinhardt
2022-11-17  5:46   ` [PATCH v6 2/7] refs: get rid of global list of hidden refs Patrick Steinhardt
2022-11-17  5:46   ` [PATCH v6 3/7] revision: move together exclusion-related functions Patrick Steinhardt
2022-11-17  5:46   ` [PATCH v6 4/7] revision: introduce struct to handle exclusions Patrick Steinhardt
2022-11-17  5:46   ` [PATCH v6 5/7] revision: add new parameter to exclude hidden refs Patrick Steinhardt
2022-11-17  5:47   ` [PATCH v6 6/7] rev-parse: add `--exclude-hidden=` option Patrick Steinhardt
2022-11-17  5:47   ` [PATCH v6 7/7] receive-pack: only use visible refs for connectivity check Patrick Steinhardt
2022-11-17 15:03   ` [PATCH v6 0/7] " Jeff King
2022-11-17 21:24     ` Taylor Blau

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=221028.867d0k7yny.gmgdl@evledraar.gmail.com \
    --to=avarab@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=ps@pks.im \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).