Refactor fetch negotiation into its own API

If tag following is required when using a transport that does not support tag following, fetch_pack() will be invoked twice in the same process, necessitating a clearing of the object flags used by fetch_pack() sometime during the second invocation. This is currently done in find_common(), which means that the work done by everything_local() in marking complete remote refs as COMMON_REF is wasted.

To avoid this wastage, move this clearing from find_common() to its parent function do_fetch_pack(), right before it calls everything_local().

fetch-pack.c +0 -3

@@ -336,9 +336,6 @@ static int find_common(struct fetch_pack_args *args,
 
 	if (args->stateless_rpc && multi_ack == 1)
 		die(_("--stateless-rpc requires multi_ack_detailed"));
-	if (marked)
-		for_each_ref(clear_marks, NULL);
-	marked = 1;
 
 	for_each_ref(rev_list_insert_ref_oid, NULL);
 	for_each_cached_alternate(insert_one_alternate_object);

Hi,

Quoted 11 lines · Jonathan Tan

If tag following is required when using a transport that does not support tag following, fetch_pack() will be invoked twice in the same process, necessitating a clearing of the object flags used by fetch_pack() sometime during the second invocation. This is currently done in find_common(), which means that the work done by everything_local() in marking complete remote refs as COMMON_REF is wasted.

To avoid this wastage, move this clearing from find_common() to its parent function do_fetch_pack(), right before it calls everything_local().

I had to read this a few times and didn't end up understanding it.

Is the idea that this will speed something up? Can you provide e.g. "perf stat" output (or even a new perf test in t/perf) demonstrating the improvement? Or is it a cleanup?

As an experiment, I tried applying the '-' part of the change without the '+' part to get confidence that tests cover this well. To my chagrin, all tests still passed. :/

In the preimage, we call clear_marks in find_common. This is right before we start setting up the revision walk, e.g. by inserting revisions for each ref. In the postimage, we call clear_marks in do_fetch_pack. This is right before we call everything_local.

I end up feeling that I don't understand the code well, neither before nor after the patch. Ideas for making it clearer?

When "ACK %s ready" is received, find_common() clears rev_list in an attempt to stop further "have" lines from being sent [1]. This appears to work, despite the invocation to mark_common() in the "while" loop.

Though it is possible for mark_common() to invoke rev_list_push() (thus making rev_list non-empty once more), it is more likely that the commits

in rev_list that have un-SEEN parents are also unparsed, meaning that mark_common() is not invoked on them.

To avoid all this uncertainty, it is better to explicitly end the loop when "ACK %s ready" is received instead of clearing rev_list. Remove the clearing of rev_list and write "if (got_ready) break;" instead.

The corresponding code for protocol v2 in process_acks() does not have the same problem, because the invoker of process_acks() (do_fetch_pack_v2()) proceeds immediately to processing the packfile

upon "ACK %s ready". The clearing of rev_list here is thus redundant, and this patch also removes it.

[1] The rationale is further described in the originating commit f2cba9299b ("fetch-pack: Finish negotation if remote replies "ACK %s ready"", 2011-03-14).

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

+++ b/fetch-pack.c

fetch-pack.c +1 -3

@@ -517,10 +517,8 @@ static int find_common(struct fetch_pack_args *args,
 					mark_common(commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
-					if (ack == ACK_ready) {
-						clear_prio_queue(&rev_list);
+					if (ack == ACK_ready)
 						got_ready = 1;
-					}
 					break;
 					}
 				}

Quoted 3 lines · Jonathan Tan

The corresponding code for protocol v2 in process_acks() does not have the same problem, because the invoker of process_acks() (do_fetch_pack_v2()) proceeds immediately to processing the packfile

nit: s/proceeds/procedes/

Hi,

Quoted 3 lines · Jonathan Tan

When "ACK %s ready" is received, find_common() clears rev_list in an attempt to stop further "have" lines from being sent [1]. This appears to work, despite the invocation to mark_common() in the "while" loop.

Does "appears to work" mean "works" or "doesn't work but does an okay job of faking"?

Quoted 2 lines

Though it is possible for mark_common() to invoke rev_list_push() (thus making rev_list non-empty once more), it is more likely that the commits

nit: s/more likely/most likely/
or s/it is more likely that/usually/

Quoted 3 lines

in rev_list that have un-SEEN parents are also unparsed, meaning that mark_common() is not invoked on them.

Quoted 3 lines

To avoid all this uncertainty, it is better to explicitly end the loop when "ACK %s ready" is received instead of clearing rev_list. Remove the clearing of rev_list and write "if (got_ready) break;" instead.

I'm still a little curious about whether this can happen in practice or whether it's just about readability (or whether you didn't figure out which, which is perfectly fine), but either way it's a good change.

fetch-pack.c static int process_acks(struct packet_reader *reader, struct oidset *common) · line 1285

Quoted 7 lines

fetch-pack.c +0 -1

@@ -1281,7 +1281,6 @@ static int process_acks(struct packet_reader *reader, struct oidset *common)
 		}
 
 		if (!strcmp(reader->line, "ready")) {
-			clear_prio_queue(&rev_list);
 			received_ready = 1;
 			continue;

I'm curious about the lifetime of &rev_list. Does the priority queue get freed eventually?

In do_fetch_pack_v2(), rev_list_insert_ref_oid() is invoked before everything_local(). This means that if we have a commit that is both our ref and their ref, it would be enqueued by rev_list_insert_ref_oid() as SEEN, and since it is thus already SEEN, everything_local() would not enqueue it.

If everything_local() were invoked first, as it is in do_fetch_pack() for protocol v0, then everything_local() would enqueue it with COMMON_REF | SEEN. The addition of COMMON_REF ensures that its parents are not sent as "have" lines.

Change the order in do_fetch_pack_v2() to be consistent with do_fetch_pack(), and to avoid sending unnecessary "have" lines.

fetch-pack.c +0 -1

@@ -1372,14 +1372,14 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 				for_each_ref(clear_marks, NULL);
 			marked = 1;
 
-			for_each_ref(rev_list_insert_ref_oid, NULL);

I get lost in the above description. I suspect it's doing a good job of describing the code, instead of answering the question I really have about what is broken and what behavior we want instead.

E.g. are there some commands that I can run to trigger the unnecessary "have" lines? That would make it easier for me to understand the rest and whether this is a good approach for suppressing them.

It's possible I should be skipping to the test, but a summary in the commit message would make life easier for lazy people like me. :)

This is subtle. My instinct would be to assume that the purpose of everything_local is just to determine whether we need to send a fetch request, but it appears we also want to rely on a side effect from it.

Could everything_local get a function comment to describe what side effects we will be counting on from it?

nit: this adds the new test as last in the script. Is there some logical earlier place in the file it can go instead? That way, the file stays organized and concurrent patches that modify the same test script are less likely to conflict.

t/t5500-fetch-pack.sh test_expect_success 'fetch with --filter=blob:limit=0' ' · line 816

Quoted 5 lines

t/t5500-fetch-pack.sh +5 -0

+     rm -rf server client &&
+     git init server &&
+     test_commit -C server aref_both_1 &&
+     git -C server tag -d aref_both_1 &&
+     test_commit -C server aref_both_2 &&

What does aref stand for?

t/t5500-fetch-pack.sh test_expect_success 'fetch with --filter=blob:limit=0' ' · line 821

Quoted 5 lines

t/t5500-fetch-pack.sh +5 -0

+
+     # The ref name that only the server has must be a prefix of all the
+     # others, to ensure that the client has the same information regardless
+     # of whether protocol v0 (which does not have ref prefix filtering) or
+     # protocol v2 (which does) is used.

must or else what? Maybe:

# In this test, the ref name that only the server has is a prefix of # all other refs. This ensures that the client has the same information # regardless of [etc]

t/t5500-fetch-pack.sh test_expect_success 'fetch with --filter=blob:limit=0' ' · line 827

Quoted 6 lines

t/t5500-fetch-pack.sh +6 -0

+     git clone server client &&
+     test_commit -C server aref &&
+     test_commit -C client aref_client &&
+
+     # In both protocol v0 and v2, ensure that the parent of aref_both_2 is
+     # not sent as a "have" line.

Why shouldn't it be sent as a "have" line? E.g. does another "have" line make it redundant?

t/t5500-fetch-pack.sh test_expect_success 'fetch with --filter=blob:limit=0' ' · line 834

Quoted 7 lines

t/t5500-fetch-pack.sh +7 -0

+
+     rm -f trace &&
+     cp -r client clientv0 &&
+     GIT_TRACE_PACKET="$(pwd)/trace" git -C clientv0 \
+             fetch origin aref &&
+     grep "have $(git -C client rev-parse aref_client)" trace &&
+     grep "have $(git -C client rev-parse aref_both_2)" trace &&

nit: can make this more robust by doing

        aref_client=$(git -C client rev-parse aref_client) &&
        aref_both_2=$(git -C client rev-parse aref_both_2) &&

since this way if the git command fails, the test fails.

Reduce the number of global variables by making the priority queue and the count of non-common commits in it local, passing them as a struct to various functions where necessary.

This also helps in the case that fetch_pack() is invoked twice in the same process (when tag following is required when using a transport that does not support tag following), in that different priority queues will now be used in each invocation, instead of reusing the possibly non-empty one.

The struct containing these variables is named "data" to ease review of a subsequent patch in this series - in that patch, this struct definition and several functions will be moved to a negotiation-specific file, and this allows the move to be verbatim.

Quoted 3 lines · Jonathan Tan

Reduce the number of global variables by making the priority queue and the count of non-common commits in it local, passing them as a struct to various functions where necessary.

\o/

Quoted 6 lines

This also helps in the case that fetch_pack() is invoked twice in the same process (when tag following is required when using a transport that does not support tag following), in that different priority queues will now be used in each invocation, instead of reusing the possibly non-empty one.

Quoted 4 lines

The struct containing these variables is named "data" to ease review of a subsequent patch in this series - in that patch, this struct definition and several functions will be moved to a negotiation-specific file, and this allows the move to be verbatim.

Hm. Is the idea that 'struct data' gets stored in the opaque 'data' member of the fetch_negotiator?

'struct data' is a quite vague type name --- it's almost equivalent to 'void' (which I suppose is the idea). How about something like 'struct negotiation_data' or 'fetch_negotiator_data' in this patch? That way this last paragraph of the commit message wouldn't be needed.

[...]

Quoted 6 lines

fetch-pack.c +0 -0

@@ -50,8 +50,12 @@ static int marked;
  */
 #define MAX_IN_VAIN 256
 

fetch-pack.c static int marked; · line 56

Quoted 6 lines

fetch-pack.c +4 -2

-static struct prio_queue rev_list = { compare_commits_by_commit_date };
-static int non_common_revs, multi_ack, use_sideband;
+struct data {
+     struct prio_queue rev_list;
+     int non_common_revs;
+};

How does this struct get used? What does it represent? A comment might help.

This enables the calculation of was_common and the invocation to mark_common() to be abstracted into a single call to the negotiator API (to be introduced in a subsequent patch).

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

I like it. I think it should be possible to describe the benefit of this patch without reference to the specifics of the subsequent one. Maybe something like:

When receiving 'ACK <object-id> continue' for a common commit, check if the commit was already known to be common and mark it as such if not up front. This should make future refactoring of how the information about common commits is stored more straightforward.

No visible change intended.

Introduce the new files fetch-negotiator.{h,c}, which contains an API behind which the details of negotiation are abstracted. Currently, only one algorithm is available: the existing one.

This patch is written to be more easily reviewed: static functions are moved verbatim from fetch-pack.c to negotiator/default.c, and it can be seen that the lines replaced by negotiator->X() calls are present in the X() functions respectively.

Signed-off-by Jonathan Tan <[email protected]>

---
 Makefile             |   2 +
 fetch-negotiator.c   |   7 ++
 fetch-negotiator.h   |  45 ++++++++++
 fetch-pack.c         | 207 ++++++++++---------------------------------
 negotiator/default.c | 173 ++++++++++++++++++++++++++++++++++++
 negotiator/default.h |   8 ++
 object.h             |   3 +-
 7 files changed, 282 insertions(+), 163 deletions(-)
 create mode 100644 fetch-negotiator.c
 create mode 100644 fetch-negotiator.h
 create mode 100644 negotiator/default.c
 create mode 100644 negotiator/default.h

fetch-negotiator.c new file +1 -0

+++ b/fetch-pack.c

fetch-negotiator.c new file +1 -4

@@ -1061,19 +944,17 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	if (!server_supports("deepen-relative") && args->deepen_relative)
 		die(_("Server does not support --deepen"));
 
-	if (marked)
-		for_each_ref(clear_marks, NULL);
-	marked = 1;
-	if (everything_local(&data, args, &ref, sought, nr_sought)) {
+	if (everything_local(&negotiator, args, &ref, sought, nr_sought)) {
 		packet_flush(fd[1]);

Quoted 4 lines

This patch is written to be more easily reviewed: static functions are moved verbatim from fetch-pack.c to negotiator/default.c, and it can be seen that the lines replaced by negotiator->X() calls are present in the X() functions respectively.

nit: s/more//

Quoted 1 line

+#include "fetch-negotiator.h"

To avoid various standards weirdness, the first #include in all files should be git-compat-util.h, cache.h, or builtin.h. I tend to just use git-compat-util.h.

Quoted 1 line

+#include "cache.h"

What does this need from cache.h?

Quoted 1 line

+#include "commit.h"

optional: could use a forward-declaration "struct commit;" since we only use pointers instead of the complete type. Do we document when to prefer forward-declaration and when to #include complete type definitions somewhere?

[...]

Quoted 1 line

+struct fetch_negotiator {

Neat. Can this file include an overview of the calling sequence / how I use this API? E.g.

/*
* Standard calling sequence:
* 1. Obtain a struct fetch_negotiator * using [...]
* 2. For each [etc]
* 3. Free resources associated with the negotiator by calling
* release(this). This frees the pointer; it cannot be
* reused.
*/

That would be a good complement to the reference documentation in the struct definition.

Quoted 15 lines

fetch-pack.c +2 -5

@@ -1061,19 +944,17 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
      if (!server_supports("deepen-relative") && args->deepen_relative)
              die(_("Server does not support --deepen"));
 
-     if (marked)
-             for_each_ref(clear_marks, NULL);
-     marked = 1;
-     if (everything_local(&data, args, &ref, sought, nr_sought)) {
+     if (everything_local(&negotiator, args, &ref, sought, nr_sought)) {
              packet_flush(fd[1]);
              goto all_done;
      }
-     if (find_common(&data, args, fd, &oid, ref) < 0)
+     if (find_common(&negotiator, args, fd, &oid, ref) < 0)
              if (!args->keep_pack)

fetch-pack.c static struct ref *do_fetch_pack(struct fetch_pack_args *args, · line 957

Quoted 5 lines

fetch-pack.c +1 -0

                      /* When cloning, it is not unusual to have
                       * no common commit.
                       */
                      warning(_("no common commits"));
+     negotiator.release(&negotiator);

Should this go after the all_done so that it doesn't get bypassed in the everything_local case?

fetch-pack.c static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args, · line 1321

Quoted 7 lines

fetch-pack.c +1 -0

@@ -1434,6 +1316,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
                      continue;
              }
      }
+     negotiator.release(&negotiator);
 
      oidset_clear(&common);

nit: could put the negotiator.release(&negotiator) after the blank line, in the same paragraph as the other free calls like oidset_clear(&common).

negotiator/default.c line 1

Quoted 3 lines

negotiator/default.c new file +2 -0

+++ b/negotiator/default.c

@@ -0,0 +1,173 @@
+#include "default.h"

First #include should be "git-compat-util.h".

[...]

negotiator/default.c line 49

Quoted 5 lines

negotiator/default.c new file +5 -0

+/*
+   This function marks a rev and its ancestors as common.
+   In some cases, it is desirable to mark only the ancestors (for example
+   when only the server does not yet know that they are common).
+*/

Not about this change: comments should have ' *' at the start of each line (could do in a preparatory patch or a followup).

Quoted 4 lines

negotiator/default.h new file +1 -0

@@ -0,0 +1,8 @@
+#ifndef NEGOTIATOR_DEFAULT_H

negotiator/default.h line 6

Quoted 5 lines

negotiator/default.h new file +5 -0

+#define NEGOTIATOR_DEFAULT_H
+
+#include "fetch-negotiator.h"
+
+void default_negotiator_init(struct fetch_negotiator *negotiator);

optional: same question about whether to use a forward declaration as in fetch-negotiator.h.

Quoted 4 lines

nit: this adds the new test as last in the script. Is there some logical earlier place in the file it can go instead? That way, the file stays organized and concurrent patches that modify the same test script are less likely to conflict.

Good point. I'll find a place.

Quoted 9 lines

Review

Quoted 6 lines

(quoted diff) +4 -2

-static struct prio_queue rev_list = { compare_commits_by_commit_date };
-static int non_common_revs, multi_ack, use_sideband;
+struct data {
+     struct prio_queue rev_list;
+     int non_common_revs;
+};

How does this struct get used? What does it represent? A comment might help.

I'll add a comment.

Quoted 8 lines

Review

Quoted 5 lines

(quoted diff) +5 -0

+/*
+   This function marks a rev and its ancestors as common.
+   In some cases, it is desirable to mark only the ancestors (for example
+   when only the server does not yet know that they are common).
+*/

Not about this change: comments should have ' *' at the start of each line (could do in a preparatory patch or a followup).

I'll add a followup.

The function everything_local(), despite its name, also (1) marks commits as COMPLETE and COMMON_REF and (2) invokes filter_refs() as important side effects. Extract (1) into its own function (mark_complete_and_common_ref()) and remove
(2).

The restoring of save_commit_buffer, which was introduced in a1c6d7c1a7 ("fetch-pack: restore save_commit_buffer after use", 2017-12-08), is a concern of the parse_object() call in mark_complete_and_common_ref(), so it has been moved from the end of everything_local() to the end of mark_complete_and_common_ref().

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 39 ++++++++++++++++++++++++++++++---------
 1 file changed, 30 insertions(+), 9 deletions(-)

fetch-pack.c +30 -9

index a320ce987..5c87bb8bb 100644
@@ -734,12 +734,20 @@ static int add_loose_objects_to_set(const struct object_id *oid,
 	return 0;
 }
 
-static int everything_local(struct fetch_pack_args *args,
-			    struct ref **refs,
-			    struct ref **sought, int nr_sought)
+/*
+ * Mark recent commits available locally and reachable from a local ref as
+ * COMPLETE. If args->no_dependents is false, also mark COMPLETE remote refs as
+ * COMMON_REF (otherwise, we are not planning to participate in negotiation, and
+ * thus do not need COMMON_REF marks).
+ *
+ * The cutoff time for recency is determined by this heuristic: it is the
+ * earliest commit time of the objects in refs that are commits and that we know
+ * the commit time of.
+ */
+static void mark_complete_and_common_ref(struct fetch_pack_args *args,
+					 struct ref **refs)
 {
 	struct ref *ref;
-	int retval;
 	int old_save_commit_buffer = save_commit_buffer;
 	timestamp_t cutoff = 0;
 	struct oidset loose_oid_set = OIDSET_INIT;

@@ -812,7 +820,18 @@ static int everything_local(struct fetch_pack_args *args,
 		}
 	}
 
-	filter_refs(args, refs, sought, nr_sought);
+	save_commit_buffer = old_save_commit_buffer;
+}
+
+/*
+ * Returns 1 if every object pointed to by the given remote refs is available
+ * locally and reachable from a local ref, and 0 otherwise.
+ */
+static int everything_local(struct fetch_pack_args *args,
+			    struct ref **refs)
+{
+	struct ref *ref;
+	int retval;
 
 	for (retval = 1, ref = *refs; ref ; ref = ref->next) {
 		const struct object_id *remote = &ref->old_oid;

@@ -829,8 +848,6 @@ static int everything_local(struct fetch_pack_args *args,
 			      ref->name);
 	}
 
-	save_commit_buffer = old_save_commit_buffer;
-
 	return retval;
 }
 

@@ -1053,7 +1070,9 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	if (!server_supports("deepen-relative") && args->deepen_relative)
 		die(_("Server does not support --deepen"));
 
-	if (everything_local(args, &ref, sought, nr_sought)) {
+	mark_complete_and_common_ref(args, &ref);
+	filter_refs(args, &ref, sought, nr_sought);
+	if (everything_local(args, &ref)) {
 		packet_flush(fd[1]);
 		goto all_done;
 	}

@@ -1377,7 +1396,9 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			for_each_cached_alternate(insert_one_alternate_object);
 
 			/* Filter 'ref' by 'sought' and those that aren't local */
-			if (everything_local(args, &ref, sought, nr_sought))
+			mark_complete_and_common_ref(args, &ref);
+			filter_refs(args, &ref, sought, nr_sought);
+			if (everything_local(args, &ref))
 				state = FETCH_DONE;
 			else
 				state = FETCH_SEND_REQUEST;

Signature · 1 line

2.17.0.768.g1526ddbba1.dirty

When "ACK %s ready" is received, find_common() clears rev_list in an attempt to stop further "have" lines from being sent [1]. It is much more readable to explicitly break from the loop instead, so do this.

This means that the memory in priority queue will be reclaimed only upon program exit, similar to the cases in which "ACK %s ready" is not

received. (A related problem occurs when do_fetch_pack() is invoked a second time in the same process with a possibly non-empty priority queue, but this will be solved in a subsequent patch in this patch set.)

[1] The rationale is further described in the originating commit f2cba9299b ("fetch-pack: Finish negotation if remote replies "ACK %s ready"", 2011-03-14).

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

fetch-pack.c +3 -4

index 2812499a5..09f5c83c4 100644
@@ -517,10 +517,8 @@ static int find_common(struct fetch_pack_args *args,
 					mark_common(commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
-					if (ack == ACK_ready) {
-						clear_prio_queue(&rev_list);
+					if (ack == ACK_ready)
 						got_ready = 1;
-					}
 					break;
 					}
 				}

@@ -530,6 +528,8 @@ static int find_common(struct fetch_pack_args *args,
 				print_verbose(args, _("giving up"));
 				break; /* give up */
 			}
+			if (got_ready)
+				break;
 		}
 	}
 done:

@@ -1300,7 +1300,6 @@ static int process_acks(struct packet_reader *reader, struct oidset *common)
 		}
 
 		if (!strcmp(reader->line, "ready")) {
-			clear_prio_queue(&rev_list);
 			received_ready = 1;
 			continue;
 		}

Signature · 1 line

2.17.0.768.g1526ddbba1.dirty

Quoted 6 lines · Jonathan Tan

When "ACK %s ready" is received, find_common() clears rev_list in an attempt to stop further "have" lines from being sent [1]. It is much more readable to explicitly break from the loop instead, so do this.

This means that the memory in priority queue will be reclaimed only upon program exit, similar to the cases in which "ACK %s ready" is not

This seems fine for now though ideally we would remove the global priority queue and have it live on the stack somewhere in the call stack and it could be cleared unconditionally before returning.

Quoted 50 lines

received. (A related problem occurs when do_fetch_pack() is invoked a second time in the same process with a possibly non-empty priority queue, but this will be solved in a subsequent patch in this patch set.)

[1] The rationale is further described in the originating commit f2cba9299b ("fetch-pack: Finish negotation if remote replies "ACK %s ready"", 2011-03-14).

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

fetch-pack.c +3 -4

index 2812499a5..09f5c83c4 100644
@@ -517,10 +517,8 @@ static int find_common(struct fetch_pack_args *args,
 					mark_common(commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
-					if (ack == ACK_ready) {
-						clear_prio_queue(&rev_list);
+					if (ack == ACK_ready)
 						got_ready = 1;
-					}
 					break;
 					}
 				}

@@ -530,6 +528,8 @@ static int find_common(struct fetch_pack_args *args,
 				print_verbose(args, _("giving up"));
 				break; /* give up */
 			}
+			if (got_ready)
+				break;
 		}
 	}
 done:

@@ -1300,7 +1300,6 @@ static int process_acks(struct packet_reader *reader, struct oidset *common)
 		}
 
 		if (!strcmp(reader->line, "ready")) {
-			clear_prio_queue(&rev_list);
 			received_ready = 1;
 			continue;
 		}

Signature · 1 line

2.17.0.768.g1526ddbba1.dirty

Signature · 1 line

Brandon Williams

In negotiation using protocol v2, fetch-pack sometimes does not make full use of the information obtained in the ref advertisement:
specifically, that if the server advertises a commit that the client also has, the client never needs to inform the server that it has the commit's parents, since it can just tell the server that it has the advertised commit and it knows that the server can and will infer the rest.

This is because, in do_fetch_pack_v2(), rev_list_insert_ref_oid() is invoked before everything_local(). This means that if we have a commit that is both our ref and their ref, it would be enqueued by rev_list_insert_ref_oid() as SEEN, and since it is thus already SEEN, everything_local() would not enqueue it.

If everything_local() were invoked first, as it is in do_fetch_pack() for protocol v0, then everything_local() would enqueue it with COMMON_REF | SEEN. The addition of COMMON_REF ensures that its parents are not sent as "have" lines.

Change the order in do_fetch_pack_v2() to be consistent with do_fetch_pack(), and to avoid sending unnecessary "have" lines.

Signed-off-by Jonathan Tan <[email protected]>

---

t/t5500-fetch-pack.sh +26 -0

+	git clone server client &&
+	test_commit -C server bo &&
+	test_commit -C client client_has &&
+
+	# In both protocol v0 and v2, ensure that the parent of both_have_2 is
+	# not sent as a "have" line. The client should know that the server has
+	# both_have_2, so it only needs to inform the server that it has
+	# both_have_2, and the server can infer the rest.
+
+	rm -f trace &&
+	cp -r client clientv0 &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C clientv0 \
+		fetch origin bo &&
 
+	grep "have $(git -C client rev-parse client_has)" trace &&
+	grep "have $(git -C client rev-parse both_have_2)" trace &&
+	! grep "have $(git -C client rev-parse both_have_2^)" trace &&
+
+	rm -f trace &&
+	cp -r client clientv2 &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C clientv2 -c protocol.version=2 \
+		fetch origin bo &&
+	grep "have $(git -C client rev-parse client_has)" trace &&
+	grep "have $(git -C client rev-parse both_have_2)" trace &&
+	! grep "have $(git -C client rev-parse both_have_2^)" trace
+'
+
 test_expect_success 'filtering by size' '
 	rm -rf server client &&
 	test_create_repo server &&

Reduce the number of global variables by making the priority queue and the count of non-common commits in it local, passing them as a struct to various functions where necessary.

This also helps in the case that fetch_pack() is invoked twice in the same process (when tag following is required when using a transport that does not support tag following), in that different priority queues will now be used in each invocation, instead of reusing the possibly non-empty one.

The struct containing these variables is named "data" to ease review of a subsequent patch in this series - in that patch, this struct definition and several functions will be moved to a negotiation-specific file, and this allows the move to be verbatim.

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 104 +++++++++++++++++++++++++++++----------------------
 1 file changed, 59 insertions(+), 45 deletions(-)

fetch-pack.c +59 -45

index 114207b8e..c31644bb9 100644
@@ -50,8 +50,12 @@ static int marked;
  */
 #define MAX_IN_VAIN 256
 
-static struct prio_queue rev_list = { compare_commits_by_commit_date };
-static int non_common_revs, multi_ack, use_sideband;
+struct data {
+	struct prio_queue rev_list;
+	int non_common_revs;
+};
+
+static int multi_ack, use_sideband;
 /* Allow specifying sha1 if it is a ref tip. */
 #define ALLOW_TIP_SHA1	01
 /* Allow request of a sha1 if it is reachable from a ref (possibly hidden ref). */

@@ -93,7 +97,8 @@ static void cache_one_alternate(const char *refname,
 	cache->items[cache->nr++] = obj;
 }
 
-static void for_each_cached_alternate(void (*cb)(struct object *))
+static void for_each_cached_alternate(struct data *data,
+				      void (*cb)(struct data *, struct object *))
 {
 	static int initialized;
 	static struct alternate_object_cache cache;

@@ -105,10 +110,10 @@ static void for_each_cached_alternate(void (*cb)(struct object *))
 	}
 
 	for (i = 0; i < cache.nr; i++)
-		cb(cache.items[i]);
+		cb(data, cache.items[i]);
 }
 
-static void rev_list_push(struct commit *commit, int mark)
+static void rev_list_push(struct data *data, struct commit *commit, int mark)
 {
 	if (!(commit->object.flags & mark)) {
 		commit->object.flags |= mark;

@@ -116,19 +121,20 @@ static void rev_list_push(struct commit *commit, int mark)
 		if (parse_commit(commit))
 			return;
 
-		prio_queue_put(&rev_list, commit);
+		prio_queue_put(&data->rev_list, commit);
 
 		if (!(commit->object.flags & COMMON))
-			non_common_revs++;
+			data->non_common_revs++;
 	}
 }
 
-static int rev_list_insert_ref(const char *refname, const struct object_id *oid)
+static int rev_list_insert_ref(struct data *data, const char *refname,
+			       const struct object_id *oid)
 {
 	struct object *o = deref_tag(parse_object(oid), refname, 0);
 
 	if (o && o->type == OBJ_COMMIT)
-		rev_list_push((struct commit *)o, SEEN);
+		rev_list_push(data, (struct commit *)o, SEEN);
 
 	return 0;
 }

@@ -136,7 +142,7 @@ static int rev_list_insert_ref(const char *refname, const struct object_id *oid)
 static int rev_list_insert_ref_oid(const char *refname, const struct object_id *oid,
 				   int flag, void *cb_data)
 {
-	return rev_list_insert_ref(refname, oid);
+	return rev_list_insert_ref(cb_data, refname, oid);
 }
 
 static int clear_marks(const char *refname, const struct object_id *oid,

@@ -156,7 +162,7 @@ static int clear_marks(const char *refname, const struct object_id *oid,
    when only the server does not yet know that they are common).
 */
 
-static void mark_common(struct commit *commit,
+static void mark_common(struct data *data, struct commit *commit,
 		int ancestors_only, int dont_parse)
 {
 	if (commit != NULL && !(commit->object.flags & COMMON)) {

@@ -166,12 +172,12 @@ static void mark_common(struct commit *commit,
 			o->flags |= COMMON;
 
 		if (!(o->flags & SEEN))
-			rev_list_push(commit, SEEN);
+			rev_list_push(data, commit, SEEN);
 		else {
 			struct commit_list *parents;
 
 			if (!ancestors_only && !(o->flags & POPPED))
-				non_common_revs--;
+				data->non_common_revs--;
 			if (!o->parsed && !dont_parse)
 				if (parse_commit(commit))
 					return;

@@ -179,7 +185,7 @@ static void mark_common(struct commit *commit,
 			for (parents = commit->parents;
 					parents;
 					parents = parents->next)
-				mark_common(parents->item, 0, dont_parse);
+				mark_common(data, parents->item, 0, dont_parse);
 		}
 	}
 }

@@ -188,7 +194,7 @@ static void mark_common(struct commit *commit,
   Get the next rev to send, ignoring the common.
 */
 
-static const struct object_id *get_rev(void)
+static const struct object_id *get_rev(struct data *data)
 {
 	struct commit *commit = NULL;
 

@@ -196,16 +202,16 @@ static const struct object_id *get_rev(void)
 		unsigned int mark;
 		struct commit_list *parents;
 
-		if (rev_list.nr == 0 || non_common_revs == 0)
+		if (data->rev_list.nr == 0 || data->non_common_revs == 0)
 			return NULL;
 
-		commit = prio_queue_get(&rev_list);
+		commit = prio_queue_get(&data->rev_list);
 		parse_commit(commit);
 		parents = commit->parents;
 
 		commit->object.flags |= POPPED;
 		if (!(commit->object.flags & COMMON))
-			non_common_revs--;
+			data->non_common_revs--;
 
 		if (commit->object.flags & COMMON) {
 			/* do not send "have", and ignore ancestors */

@@ -220,9 +226,9 @@ static const struct object_id *get_rev(void)
 
 		while (parents) {
 			if (!(parents->item->object.flags & SEEN))
-				rev_list_push(parents->item, mark);
+				rev_list_push(data, parents->item, mark);
 			if (mark & COMMON)
-				mark_common(parents->item, 1, 0);
+				mark_common(data, parents->item, 1, 0);
 			parents = parents->next;
 		}
 	}

@@ -296,9 +302,9 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_object(struct object *obj)
+static void insert_one_alternate_object(struct data *data, struct object *obj)
 {
-	rev_list_insert_ref(NULL, &obj->oid);
+	rev_list_insert_ref(data, NULL, &obj->oid);
 }
 
 #define INITIAL_FLUSH 16

@@ -321,7 +327,7 @@ static int next_flush(int stateless_rpc, int count)
 	return count;
 }
 
-static int find_common(struct fetch_pack_args *args,
+static int find_common(struct data *data, struct fetch_pack_args *args,
 		       int fd[2], struct object_id *result_oid,
 		       struct ref *refs)
 {

@@ -337,8 +343,8 @@ static int find_common(struct fetch_pack_args *args,
 	if (args->stateless_rpc && multi_ack == 1)
 		die(_("--stateless-rpc requires multi_ack_detailed"));
 
-	for_each_ref(rev_list_insert_ref_oid, NULL);
-	for_each_cached_alternate(insert_one_alternate_object);
+	for_each_ref(rev_list_insert_ref_oid, data);
+	for_each_cached_alternate(data, insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {

@@ -456,7 +462,7 @@ static int find_common(struct fetch_pack_args *args,
 	retval = -1;
 	if (args->no_dependents)
 		goto done;
-	while ((oid = get_rev())) {
+	while ((oid = get_rev(data))) {
 		packet_buf_write(&req_buf, "have %s\n", oid_to_hex(oid));
 		print_verbose(args, "have %s", oid_to_hex(oid));
 		in_vain++;

@@ -514,7 +520,7 @@ static int find_common(struct fetch_pack_args *args,
 					} else if (!args->stateless_rpc
 						   || ack != ACK_common)
 						in_vain = 0;
-					mark_common(commit, 0, 1);
+					mark_common(data, commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
 					if (ack == ACK_ready)

@@ -704,7 +710,7 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(struct object *obj)
+static void mark_alternate_complete(struct data *unused, struct object *obj)
 {
 	mark_complete(&obj->oid);
 }

@@ -741,7 +747,8 @@ static int add_loose_objects_to_set(const struct object_id *oid,
  * earliest commit time of the objects in refs that are commits and that we know
  * the commit time of.
  */
-static void mark_complete_and_common_ref(struct fetch_pack_args *args,
+static void mark_complete_and_common_ref(struct data *data,
+					 struct fetch_pack_args *args,
 					 struct ref **refs)
 {
 	struct ref *ref;

@@ -792,7 +799,7 @@ static void mark_complete_and_common_ref(struct fetch_pack_args *args,
 	if (!args->no_dependents) {
 		if (!args->deepen) {
 			for_each_ref(mark_complete_oid, NULL);
-			for_each_cached_alternate(mark_alternate_complete);
+			for_each_cached_alternate(NULL, mark_alternate_complete);
 			commit_list_sort_by_date(&complete);
 			if (cutoff)
 				mark_recent_complete_commits(args, cutoff);

@@ -810,9 +817,10 @@ static void mark_complete_and_common_ref(struct fetch_pack_args *args,
 				continue;
 
 			if (!(o->flags & SEEN)) {
-				rev_list_push((struct commit *)o, COMMON_REF | SEEN);
+				rev_list_push(data, (struct commit *)o,
+					      COMMON_REF | SEEN);
 
-				mark_common((struct commit *)o, 1, 1);
+				mark_common(data, (struct commit *)o, 1, 1);
 			}
 		}
 	}

@@ -995,6 +1003,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	struct object_id oid;
 	const char *agent_feature;
 	int agent_len;
+	struct data data = { { compare_commits_by_commit_date } };
 
 	sort_ref_list(&ref, ref_compare_name);
 	QSORT(sought, nr_sought, cmp_ref_by_name);

@@ -1070,13 +1079,13 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	if (marked)
 		for_each_ref(clear_marks, NULL);
 	marked = 1;
-	mark_complete_and_common_ref(args, &ref);
+	mark_complete_and_common_ref(&data, args, &ref);
 	filter_refs(args, &ref, sought, nr_sought);
 	if (everything_local(args, &ref)) {
 		packet_flush(fd[1]);
 		goto all_done;
 	}
-	if (find_common(args, fd, &oid, ref) < 0)
+	if (find_common(&data, args, fd, &oid, ref) < 0)
 		if (!args->keep_pack)
 			/* When cloning, it is not unusual to have
 			 * no common commit.

@@ -1157,13 +1166,14 @@ static void add_common(struct strbuf *req_buf, struct oidset *common)
 	}
 }
 
-static int add_haves(struct strbuf *req_buf, int *haves_to_send, int *in_vain)
+static int add_haves(struct data *data, struct strbuf *req_buf,
+		     int *haves_to_send, int *in_vain)
 {
 	int ret = 0;
 	int haves_added = 0;
 	const struct object_id *oid;
 
-	while ((oid = get_rev())) {
+	while ((oid = get_rev(data))) {
 		packet_buf_write(req_buf, "have %s\n", oid_to_hex(oid));
 		if (++haves_added >= *haves_to_send)
 			break;

@@ -1182,7 +1192,8 @@ static int add_haves(struct strbuf *req_buf, int *haves_to_send, int *in_vain)
 	return ret;
 }
 
-static int send_fetch_request(int fd_out, const struct fetch_pack_args *args,
+static int send_fetch_request(struct data *data, int fd_out,
+			      const struct fetch_pack_args *args,
 			      const struct ref *wants, struct oidset *common,
 			      int *haves_to_send, int *in_vain)
 {

@@ -1238,7 +1249,7 @@ static int send_fetch_request(int fd_out, const struct fetch_pack_args *args,
 		add_common(&req_buf, common);
 
 		/* Add initial haves */
-		ret = add_haves(&req_buf, haves_to_send, in_vain);
+		ret = add_haves(data, &req_buf, haves_to_send, in_vain);
 	}
 
 	/* Send request */

@@ -1275,7 +1286,8 @@ static int process_section_header(struct packet_reader *reader,
 	return ret;
 }
 
-static int process_acks(struct packet_reader *reader, struct oidset *common)
+static int process_acks(struct data *data, struct packet_reader *reader,
+			struct oidset *common)
 {
 	/* received */
 	int received_ready = 0;

@@ -1294,7 +1306,7 @@ static int process_acks(struct packet_reader *reader, struct oidset *common)
 				struct commit *commit;
 				oidset_insert(common, &oid);
 				commit = lookup_commit(&oid);
-				mark_common(commit, 0, 1);
+				mark_common(data, commit, 0, 1);
 			}
 			continue;
 		}

@@ -1372,6 +1384,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 	struct packet_reader reader;
 	int in_vain = 0;
 	int haves_to_send = INITIAL_FLUSH;
+	struct data data = { { compare_commits_by_commit_date } };
 	packet_reader_init(&reader, fd[0], NULL, 0,
 			   PACKET_READ_CHOMP_NEWLINE);
 

@@ -1392,18 +1405,19 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			marked = 1;
 
 			/* Filter 'ref' by 'sought' and those that aren't local */
-			mark_complete_and_common_ref(args, &ref);
+			mark_complete_and_common_ref(&data, args, &ref);
 			filter_refs(args, &ref, sought, nr_sought);
 			if (everything_local(args, &ref))
 				state = FETCH_DONE;
 			else
 				state = FETCH_SEND_REQUEST;
 
-			for_each_ref(rev_list_insert_ref_oid, NULL);
-			for_each_cached_alternate(insert_one_alternate_object);
+			for_each_ref(rev_list_insert_ref_oid, &data);
+			for_each_cached_alternate(&data,
+						  insert_one_alternate_object);
 			break;
 		case FETCH_SEND_REQUEST:
-			if (send_fetch_request(fd[1], args, ref, &common,
+			if (send_fetch_request(&data, fd[1], args, ref, &common,
 					       &haves_to_send, &in_vain))
 				state = FETCH_GET_PACK;
 			else

@@ -1411,7 +1425,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			break;
 		case FETCH_PROCESS_ACKS:
 			/* Process ACKs/NAKs */
-			switch (process_acks(&reader, &common)) {
+			switch (process_acks(&data, &reader, &common)) {
 			case 2:
 				state = FETCH_GET_PACK;
 				break;

Signature · 1 line

2.17.0.768.g1526ddbba1.dirty

Signed-off-by Jonathan Tan <[email protected]>

---
 negotiator/default.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

negotiator/default.c +6 -8

index b8f45cf78..a9e52c943 100644
@@ -46,11 +46,10 @@ static int clear_marks(const char *refname, const struct object_id *oid,
 }
 
 /*
-   This function marks a rev and its ancestors as common.
-   In some cases, it is desirable to mark only the ancestors (for example
-   when only the server does not yet know that they are common).
-*/
-
+ * This function marks a rev and its ancestors as common.
+ * In some cases, it is desirable to mark only the ancestors (for example
+ * when only the server does not yet know that they are common).
+ */
 static void mark_common(struct data *data, struct commit *commit,
 		int ancestors_only, int dont_parse)
 {

@@ -80,9 +79,8 @@ static void mark_common(struct data *data, struct commit *commit,
 }
 
 /*
-  Get the next rev to send, ignoring the common.
-*/
-
+ * Get the next rev to send, ignoring the common.
+ */
 static const struct object_id *get_rev(struct data *data)
 {
 	struct commit *commit = NULL;

Signature · 1 line

2.17.0.768.g1526ddbba1.dirty

When "ACK %s ready" is received, find_common() clears rev_list in an attempt to stop further "have" lines from being sent [1]. It is much more readable to explicitly break from the loop instead.

So explicitly break from the loop, and make the clearing of the rev_list happen unconditionally.

[1] The rationale is further described in the originating commit f2cba9299b ("fetch-pack: Finish negotation if remote replies "ACK %s ready"", 2011-03-14).

Signed-off-by Jonathan Tan <[email protected]>

---
 fetch-pack.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

fetch-pack.c +5 -4

index 2812499a5..60adfc073 100644
@@ -517,10 +517,8 @@ static int find_common(struct fetch_pack_args *args,
 					mark_common(commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
-					if (ack == ACK_ready) {
-						clear_prio_queue(&rev_list);
+					if (ack == ACK_ready)
 						got_ready = 1;
-					}
 					break;
 					}
 				}

@@ -530,6 +528,8 @@ static int find_common(struct fetch_pack_args *args,
 				print_verbose(args, _("giving up"));
 				break; /* give up */
 			}
+			if (got_ready)
+				break;
 		}
 	}
 done:

@@ -1096,6 +1096,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 		die(_("git fetch-pack: fetch failed."));
 
  all_done:
+	clear_prio_queue(&rev_list);
 	return ref;
 }
 

@@ -1300,7 +1301,6 @@ static int process_acks(struct packet_reader *reader, struct oidset *common)
 		}
 
 		if (!strcmp(reader->line, "ready")) {
-			clear_prio_queue(&rev_list);
 			received_ready = 1;
 			continue;
 		}

@@ -1441,6 +1441,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 		}
 	}
 
+	clear_prio_queue(&rev_list);
 	oidset_clear(&common);
 	return ref;
 }