[PATCH 0/6] Refactor fetch negotiation into its own API

[PATCH 0/6] Refactor fetch negotiation into its own API

[Jonathan Tan]

Both Stefan and Junio have suggested in [1] that I create a new
negotiation API first, then implement a new algorithm, and I perhaps too
optimistically said that doing it all at once should be fine. Extracting
the API turns out to be more difficult than expected. Here are the
patches that do that, without any new algorithms.

The patches include 3 patches that eliminate some minor differences
between protocol v0 and protocol v2, then 3 patches that implement the
API. I tried to write tests for all of the former 3, but could only do
so for one, because I didn't know how to construct situations that show
a difference in behavior as an effect of such a code change (or, if such
a situation is possible without custom transports). As for the latter 3,
these are refactorings with no user-visible changes, and I have tried to
write them in such a way that it is clear to a reviewer that the same
functionality and logic is present before and after, and that they are
just organized better.

Overall, these do not change much functionality, but would be a good
base for contributors (myself and even others) to experiment with
negotiation algorithms.

[1] https://public-inbox.org/git/20180521204340.260572-1-jonathantanmy@google.com/

Jonathan Tan (6):
  fetch-pack: clear marks before everything_local()
  fetch-pack: truly stop negotiation upon ACK ready
  fetch-pack: in protocol v2, enqueue commons first
  fetch-pack: make negotiation-related vars local
  fetch-pack: move common check and marking together
  fetch-pack: introduce negotiator API

 Makefile              |   2 +
 fetch-negotiator.c    |   7 ++
 fetch-negotiator.h    |  45 +++++++++
 fetch-pack.c          | 222 ++++++++++++------------------------------
 negotiator/default.c  | 173 ++++++++++++++++++++++++++++++++
 negotiator/default.h  |   8 ++
 object.h              |   3 +-
 t/t5500-fetch-pack.sh |  35 +++++++
 8 files changed, 332 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

-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH 1/6] fetch-pack: clear marks before everything_local()

[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().

This has been occurring since the commit that introduced the clearing of
marks, 420e9af498 ("Fix tag following", 2008-03-19).

The corresponding code for protocol v2 in do_fetch_pack_v2() does not
have this problem, as the clearing of flags is done before any marking
(whether by rev_list_insert_ref_oid() or everything_local()).

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 fetch-pack.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index a320ce987..1358973a4 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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);
@@ -1053,6 +1050,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 (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
 	if (everything_local(args, &ref, sought, nr_sought)) {
 		packet_flush(fd[1]);
 		goto all_done;
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH 2/6] fetch-pack: truly stop negotiation upon ACK ready

[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.
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 <jonathantanmy@google.com>
---
 fetch-pack.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 1358973a4..2d090f612 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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:
@@ -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;
 		}
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH 3/6] fetch-pack: in protocol v2, enqueue commons first

[Jonathan Tan]

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 <jonathantanmy@google.com>
---
 fetch-pack.c          |  6 +++---
 t/t5500-fetch-pack.sh | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 3 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 2d090f612..192771a8f 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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);
-			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))
 				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);
 			break;
 		case FETCH_SEND_REQUEST:
 			if (send_fetch_request(fd[1], args, ref, &common,
diff --git a/t/t5500-fetch-pack.sh b/t/t5500-fetch-pack.sh
index 0680dec80..ad6a50ad6 100755
--- a/t/t5500-fetch-pack.sh
+++ b/t/t5500-fetch-pack.sh
@@ -808,6 +808,41 @@ test_expect_success 'fetch with --filter=blob:limit=0' '
 	fetch_filter_blob_limit_zero server server
 '
 
+test_expect_success 'use ref advertisement to prune "have" lines sent' '
+	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 &&
+
+	# 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.
+	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.
+
+	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 &&
+	! grep "have $(git -C client rev-parse aref_both_2^)" trace &&
+
+	rm -f trace &&
+	cp -r client clientv2 &&
+	GIT_TRACE_PACKET="$(pwd)/trace" git -C clientv2 -c protocol.version=2 \
+		fetch origin aref &&
+	grep "have $(git -C client rev-parse aref_client)" trace &&
+	grep "have $(git -C client rev-parse aref_both_2)" trace &&
+	! grep "have $(git -C client rev-parse aref_both_2^)" trace
+'
+
 . "$TEST_DIRECTORY"/lib-httpd.sh
 start_httpd
 
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH 4/6] fetch-pack: make negotiation-related vars local

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

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 <jonathantanmy@google.com>
---
 fetch-pack.c | 104 +++++++++++++++++++++++++++++----------------------
 1 file changed, 59 insertions(+), 45 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 192771a8f..ec92929bc 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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);
 }
@@ -731,7 +737,8 @@ static int add_loose_objects_to_set(const struct object_id *oid,
 	return 0;
 }
 
-static int everything_local(struct fetch_pack_args *args,
+static int everything_local(struct data *data,
+			    struct fetch_pack_args *args,
 			    struct ref **refs,
 			    struct ref **sought, int nr_sought)
 {
@@ -784,7 +791,7 @@ static int everything_local(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);
@@ -802,9 +809,10 @@ static int everything_local(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);
 			}
 		}
 	}
@@ -978,6 +986,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);
@@ -1053,11 +1062,11 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	if (marked)
 		for_each_ref(clear_marks, NULL);
 	marked = 1;
-	if (everything_local(args, &ref, sought, nr_sought)) {
+	if (everything_local(&data, args, &ref, sought, nr_sought)) {
 		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.
@@ -1138,13 +1147,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;
@@ -1163,7 +1173,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)
 {
@@ -1219,7 +1230,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 */
@@ -1256,7 +1267,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;
@@ -1275,7 +1287,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;
 		}
@@ -1353,6 +1365,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);
 
@@ -1373,16 +1386,17 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			marked = 1;
 
 			/* Filter 'ref' by 'sought' and those that aren't local */
-			if (everything_local(args, &ref, sought, nr_sought))
+			if (everything_local(&data, args, &ref, sought, nr_sought))
 				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
@@ -1390,7 +1404,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;
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH 5/6] fetch-pack: move common check and marking together

[Jonathan Tan]

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 <jonathantanmy@google.com>
---
 fetch-pack.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index ec92929bc..54dd3feb8 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -499,11 +499,14 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 				case ACK_continue: {
 					struct commit *commit =
 						lookup_commit(result_oid);
+					int was_common;
 					if (!commit)
 						die(_("invalid commit %s"), oid_to_hex(result_oid));
+					was_common = commit->object.flags & COMMON;
+					mark_common(data, commit, 0, 1);
 					if (args->stateless_rpc
 					 && ack == ACK_common
-					 && !(commit->object.flags & COMMON)) {
+					 && !was_common) {
 						/* We need to replay the have for this object
 						 * on the next RPC request so the peer knows
 						 * it is in common with us.
@@ -520,7 +523,6 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 					} else if (!args->stateless_rpc
 						   || ack != ACK_common)
 						in_vain = 0;
-					mark_common(data, commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
 					if (ack == ACK_ready)
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH 6/6] fetch-pack: introduce negotiator API

[Jonathan Tan]

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 <jonathantanmy@google.com>
---
 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

diff --git a/Makefile b/Makefile
index 4bca65383..8f1df08ac 100644
--- a/Makefile
+++ b/Makefile
@@ -859,6 +859,7 @@ LIB_OBJS += ewah/ewah_bitmap.o
 LIB_OBJS += ewah/ewah_io.o
 LIB_OBJS += ewah/ewah_rlw.o
 LIB_OBJS += exec-cmd.o
+LIB_OBJS += fetch-negotiator.o
 LIB_OBJS += fetch-object.o
 LIB_OBJS += fetch-pack.o
 LIB_OBJS += fsck.o
@@ -891,6 +892,7 @@ LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
 LIB_OBJS += name-hash.o
+LIB_OBJS += negotiator/default.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
diff --git a/fetch-negotiator.c b/fetch-negotiator.c
new file mode 100644
index 000000000..756c35d15
--- /dev/null
+++ b/fetch-negotiator.c
@@ -0,0 +1,7 @@
+#include "fetch-negotiator.h"
+#include "negotiator/default.h"
+
+void fetch_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	default_negotiator_init(negotiator);
+}
diff --git a/fetch-negotiator.h b/fetch-negotiator.h
new file mode 100644
index 000000000..b717b80dd
--- /dev/null
+++ b/fetch-negotiator.h
@@ -0,0 +1,45 @@
+#ifndef FETCH_NEGOTIATOR
+#define FETCH_NEGOTIATOR
+
+#include "cache.h"
+#include "commit.h"
+
+struct fetch_negotiator {
+	/*
+	 * Before negotiation starts, indicate that the server is known to have
+	 * this commit.
+	 */
+	void (*known_common)(struct fetch_negotiator *, struct commit *);
+
+	/*
+	 * Once this function is invoked, known_common() cannot be invoked any
+	 * more.
+	 *
+	 * Indicate that this commit and all its ancestors are to be checked
+	 * for commonality with the server.
+	 */
+	void (*add_tip)(struct fetch_negotiator *, struct commit *);
+
+	/*
+	 * Once this function is invoked, known_common() and add_tip() cannot
+	 * be invoked any more.
+	 *
+	 * Return the next commit that the client should send as a "have" line.
+	 */
+	const struct object_id *(*next)(struct fetch_negotiator *);
+
+	/*
+	 * Inform the negotiator that the server has the given commit. This
+	 * method must only be called on commits returned by next().
+	 */
+	int (*ack)(struct fetch_negotiator *, struct commit *);
+
+	void (*release)(struct fetch_negotiator *);
+
+	/* internal use */
+	void *data;
+};
+
+void fetch_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/fetch-pack.c b/fetch-pack.c
index 54dd3feb8..a399a62e1 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -15,10 +15,10 @@
 #include "connect.h"
 #include "transport.h"
 #include "version.h"
-#include "prio-queue.h"
 #include "sha1-array.h"
 #include "oidset.h"
 #include "packfile.h"
+#include "fetch-negotiator.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -36,13 +36,7 @@ static const char *alternate_shallow_file;
 
 /* Remember to update object flag allocation in object.h */
 #define COMPLETE	(1U << 0)
-#define COMMON		(1U << 1)
-#define COMMON_REF	(1U << 2)
-#define SEEN		(1U << 3)
-#define POPPED		(1U << 4)
-#define ALTERNATE	(1U << 5)
-
-static int marked;
+#define ALTERNATE	(1U << 1)
 
 /*
  * After sending this many "have"s if we do not get any new ACK , we
@@ -50,11 +44,6 @@ static int marked;
  */
 #define MAX_IN_VAIN 256
 
-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
@@ -97,8 +86,8 @@ static void cache_one_alternate(const char *refname,
 	cache->items[cache->nr++] = obj;
 }
 
-static void for_each_cached_alternate(struct data *data,
-				      void (*cb)(struct data *, struct object *))
+static void for_each_cached_alternate(struct fetch_negotiator *negotiator,
+				      void (*cb)(struct fetch_negotiator *, struct object *))
 {
 	static int initialized;
 	static struct alternate_object_cache cache;
@@ -110,31 +99,17 @@ static void for_each_cached_alternate(struct data *data,
 	}
 
 	for (i = 0; i < cache.nr; i++)
-		cb(data, cache.items[i]);
-}
-
-static void rev_list_push(struct data *data, struct commit *commit, int mark)
-{
-	if (!(commit->object.flags & mark)) {
-		commit->object.flags |= mark;
-
-		if (parse_commit(commit))
-			return;
-
-		prio_queue_put(&data->rev_list, commit);
-
-		if (!(commit->object.flags & COMMON))
-			data->non_common_revs++;
-	}
+		cb(negotiator, cache.items[i]);
 }
 
-static int rev_list_insert_ref(struct data *data, const char *refname,
+static int rev_list_insert_ref(struct fetch_negotiator *negotiator,
+			       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(data, (struct commit *)o, SEEN);
+		negotiator->add_tip(negotiator, (struct commit *)o);
 
 	return 0;
 }
@@ -145,97 +120,6 @@ static int rev_list_insert_ref_oid(const char *refname, const struct object_id *
 	return rev_list_insert_ref(cb_data, refname, oid);
 }
 
-static int clear_marks(const char *refname, const struct object_id *oid,
-		       int flag, void *cb_data)
-{
-	struct object *o = deref_tag(parse_object(oid), refname, 0);
-
-	if (o && o->type == OBJ_COMMIT)
-		clear_commit_marks((struct commit *)o,
-				   COMMON | COMMON_REF | SEEN | POPPED);
-	return 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).
-*/
-
-static void mark_common(struct data *data, struct commit *commit,
-		int ancestors_only, int dont_parse)
-{
-	if (commit != NULL && !(commit->object.flags & COMMON)) {
-		struct object *o = (struct object *)commit;
-
-		if (!ancestors_only)
-			o->flags |= COMMON;
-
-		if (!(o->flags & SEEN))
-			rev_list_push(data, commit, SEEN);
-		else {
-			struct commit_list *parents;
-
-			if (!ancestors_only && !(o->flags & POPPED))
-				data->non_common_revs--;
-			if (!o->parsed && !dont_parse)
-				if (parse_commit(commit))
-					return;
-
-			for (parents = commit->parents;
-					parents;
-					parents = parents->next)
-				mark_common(data, parents->item, 0, dont_parse);
-		}
-	}
-}
-
-/*
-  Get the next rev to send, ignoring the common.
-*/
-
-static const struct object_id *get_rev(struct data *data)
-{
-	struct commit *commit = NULL;
-
-	while (commit == NULL) {
-		unsigned int mark;
-		struct commit_list *parents;
-
-		if (data->rev_list.nr == 0 || data->non_common_revs == 0)
-			return NULL;
-
-		commit = prio_queue_get(&data->rev_list);
-		parse_commit(commit);
-		parents = commit->parents;
-
-		commit->object.flags |= POPPED;
-		if (!(commit->object.flags & COMMON))
-			data->non_common_revs--;
-
-		if (commit->object.flags & COMMON) {
-			/* do not send "have", and ignore ancestors */
-			commit = NULL;
-			mark = COMMON | SEEN;
-		} else if (commit->object.flags & COMMON_REF)
-			/* send "have", and ignore ancestors */
-			mark = COMMON | SEEN;
-		else
-			/* send "have", also for its ancestors */
-			mark = SEEN;
-
-		while (parents) {
-			if (!(parents->item->object.flags & SEEN))
-				rev_list_push(data, parents->item, mark);
-			if (mark & COMMON)
-				mark_common(data, parents->item, 1, 0);
-			parents = parents->next;
-		}
-	}
-
-	return &commit->object.oid;
-}
-
 enum ack_type {
 	NAK = 0,
 	ACK,
@@ -302,9 +186,10 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_object(struct data *data, struct object *obj)
+static void insert_one_alternate_object(struct fetch_negotiator *negotiator,
+					struct object *obj)
 {
-	rev_list_insert_ref(data, NULL, &obj->oid);
+	rev_list_insert_ref(negotiator, NULL, &obj->oid);
 }
 
 #define INITIAL_FLUSH 16
@@ -327,7 +212,8 @@ static int next_flush(int stateless_rpc, int count)
 	return count;
 }
 
-static int find_common(struct data *data, struct fetch_pack_args *args,
+static int find_common(struct fetch_negotiator *negotiator,
+		       struct fetch_pack_args *args,
 		       int fd[2], struct object_id *result_oid,
 		       struct ref *refs)
 {
@@ -343,8 +229,8 @@ static int find_common(struct data *data, 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, data);
-	for_each_cached_alternate(data, insert_one_alternate_object);
+	for_each_ref(rev_list_insert_ref_oid, negotiator);
+	for_each_cached_alternate(negotiator, insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
@@ -462,7 +348,7 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 	retval = -1;
 	if (args->no_dependents)
 		goto done;
-	while ((oid = get_rev(data))) {
+	while ((oid = negotiator->next(negotiator))) {
 		packet_buf_write(&req_buf, "have %s\n", oid_to_hex(oid));
 		print_verbose(args, "have %s", oid_to_hex(oid));
 		in_vain++;
@@ -502,8 +388,7 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 					int was_common;
 					if (!commit)
 						die(_("invalid commit %s"), oid_to_hex(result_oid));
-					was_common = commit->object.flags & COMMON;
-					mark_common(data, commit, 0, 1);
+					was_common = negotiator->ack(negotiator, commit);
 					if (args->stateless_rpc
 					 && ack == ACK_common
 					 && !was_common) {
@@ -712,7 +597,8 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(struct data *unused, struct object *obj)
+static void mark_alternate_complete(struct fetch_negotiator *unused,
+				    struct object *obj)
 {
 	mark_complete(&obj->oid);
 }
@@ -739,7 +625,7 @@ static int add_loose_objects_to_set(const struct object_id *oid,
 	return 0;
 }
 
-static int everything_local(struct data *data,
+static int everything_local(struct fetch_negotiator *negotiator,
 			    struct fetch_pack_args *args,
 			    struct ref **refs,
 			    struct ref **sought, int nr_sought)
@@ -810,12 +696,8 @@ static int everything_local(struct data *data,
 			if (!o || o->type != OBJ_COMMIT || !(o->flags & COMPLETE))
 				continue;
 
-			if (!(o->flags & SEEN)) {
-				rev_list_push(data, (struct commit *)o,
-					      COMMON_REF | SEEN);
-
-				mark_common(data, (struct commit *)o, 1, 1);
-			}
+			negotiator->known_common(negotiator,
+						 (struct commit *)o);
 		}
 	}
 
@@ -988,7 +870,8 @@ 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 } };
+	struct fetch_negotiator negotiator;
+	fetch_negotiator_init(&negotiator);
 
 	sort_ref_list(&ref, ref_compare_name);
 	QSORT(sought, nr_sought, cmp_ref_by_name);
@@ -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)
 			/* When cloning, it is not unusual to have
 			 * no common commit.
 			 */
 			warning(_("no common commits"));
+	negotiator.release(&negotiator);
 
 	if (args->stateless_rpc)
 		packet_flush(fd[1]);
@@ -1149,14 +1030,15 @@ static void add_common(struct strbuf *req_buf, struct oidset *common)
 	}
 }
 
-static int add_haves(struct data *data, struct strbuf *req_buf,
+static int add_haves(struct fetch_negotiator *negotiator,
+		     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(data))) {
+	while ((oid = negotiator->next(negotiator))) {
 		packet_buf_write(req_buf, "have %s\n", oid_to_hex(oid));
 		if (++haves_added >= *haves_to_send)
 			break;
@@ -1175,7 +1057,7 @@ static int add_haves(struct data *data, struct strbuf *req_buf,
 	return ret;
 }
 
-static int send_fetch_request(struct data *data, int fd_out,
+static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,
 			      const struct fetch_pack_args *args,
 			      const struct ref *wants, struct oidset *common,
 			      int *haves_to_send, int *in_vain)
@@ -1232,7 +1114,7 @@ static int send_fetch_request(struct data *data, int fd_out,
 		add_common(&req_buf, common);
 
 		/* Add initial haves */
-		ret = add_haves(data, &req_buf, haves_to_send, in_vain);
+		ret = add_haves(negotiator, &req_buf, haves_to_send, in_vain);
 	}
 
 	/* Send request */
@@ -1269,7 +1151,8 @@ static int process_section_header(struct packet_reader *reader,
 	return ret;
 }
 
-static int process_acks(struct data *data, struct packet_reader *reader,
+static int process_acks(struct fetch_negotiator *negotiator,
+			struct packet_reader *reader,
 			struct oidset *common)
 {
 	/* received */
@@ -1289,7 +1172,7 @@ static int process_acks(struct data *data, struct packet_reader *reader,
 				struct commit *commit;
 				oidset_insert(common, &oid);
 				commit = lookup_commit(&oid);
-				mark_common(data, commit, 0, 1);
+				negotiator->ack(negotiator, commit);
 			}
 			continue;
 		}
@@ -1367,7 +1250,8 @@ 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 } };
+	struct fetch_negotiator negotiator;
+	fetch_negotiator_init(&negotiator);
 	packet_reader_init(&reader, fd[0], NULL, 0,
 			   PACKET_READ_CHOMP_NEWLINE);
 
@@ -1383,22 +1267,20 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			if (args->depth > 0 || args->deepen_since || args->deepen_not)
 				args->deepen = 1;
 
-			if (marked)
-				for_each_ref(clear_marks, NULL);
-			marked = 1;
-
 			/* Filter 'ref' by 'sought' and those that aren't local */
-			if (everything_local(&data, args, &ref, sought, nr_sought))
+			if (everything_local(&negotiator, args, &ref, sought,
+					     nr_sought))
 				state = FETCH_DONE;
 			else
 				state = FETCH_SEND_REQUEST;
 
-			for_each_ref(rev_list_insert_ref_oid, &data);
-			for_each_cached_alternate(&data,
+			for_each_ref(rev_list_insert_ref_oid, &negotiator);
+			for_each_cached_alternate(&negotiator,
 						  insert_one_alternate_object);
 			break;
 		case FETCH_SEND_REQUEST:
-			if (send_fetch_request(&data, fd[1], args, ref, &common,
+			if (send_fetch_request(&negotiator, fd[1], args, ref,
+					       &common,
 					       &haves_to_send, &in_vain))
 				state = FETCH_GET_PACK;
 			else
@@ -1406,7 +1288,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			break;
 		case FETCH_PROCESS_ACKS:
 			/* Process ACKs/NAKs */
-			switch (process_acks(&data, &reader, &common)) {
+			switch (process_acks(&negotiator, &reader, &common)) {
 			case 2:
 				state = FETCH_GET_PACK;
 				break;
@@ -1434,6 +1316,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			continue;
 		}
 	}
+	negotiator.release(&negotiator);
 
 	oidset_clear(&common);
 	return ref;
diff --git a/negotiator/default.c b/negotiator/default.c
new file mode 100644
index 000000000..48d290e06
--- /dev/null
+++ b/negotiator/default.c
@@ -0,0 +1,173 @@
+#include "default.h"
+#include "../prio-queue.h"
+#include "../refs.h"
+#include "../tag.h"
+
+/* Remember to update object flag allocation in object.h */
+#define COMMON		(1U << 2)
+#define COMMON_REF	(1U << 3)
+#define SEEN		(1U << 4)
+#define POPPED		(1U << 5)
+
+static int marked;
+
+struct data {
+	struct prio_queue rev_list;
+	int non_common_revs;
+};
+
+static void rev_list_push(struct data *data, struct commit *commit, int mark)
+{
+	if (!(commit->object.flags & mark)) {
+		commit->object.flags |= mark;
+
+		if (parse_commit(commit))
+			return;
+
+		prio_queue_put(&data->rev_list, commit);
+
+		if (!(commit->object.flags & COMMON))
+			data->non_common_revs++;
+	}
+}
+
+static int clear_marks(const char *refname, const struct object_id *oid,
+		       int flag, void *cb_data)
+{
+	struct object *o = deref_tag(parse_object(oid), refname, 0);
+
+	if (o && o->type == OBJ_COMMIT)
+		clear_commit_marks((struct commit *)o,
+				   COMMON | COMMON_REF | SEEN | POPPED);
+	return 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).
+*/
+
+static void mark_common(struct data *data, struct commit *commit,
+		int ancestors_only, int dont_parse)
+{
+	if (commit != NULL && !(commit->object.flags & COMMON)) {
+		struct object *o = (struct object *)commit;
+
+		if (!ancestors_only)
+			o->flags |= COMMON;
+
+		if (!(o->flags & SEEN))
+			rev_list_push(data, commit, SEEN);
+		else {
+			struct commit_list *parents;
+
+			if (!ancestors_only && !(o->flags & POPPED))
+				data->non_common_revs--;
+			if (!o->parsed && !dont_parse)
+				if (parse_commit(commit))
+					return;
+
+			for (parents = commit->parents;
+					parents;
+					parents = parents->next)
+				mark_common(data, parents->item, 0, dont_parse);
+		}
+	}
+}
+
+/*
+  Get the next rev to send, ignoring the common.
+*/
+
+static const struct object_id *get_rev(struct data *data)
+{
+	struct commit *commit = NULL;
+
+	while (commit == NULL) {
+		unsigned int mark;
+		struct commit_list *parents;
+
+		if (data->rev_list.nr == 0 || data->non_common_revs == 0)
+			return NULL;
+
+		commit = prio_queue_get(&data->rev_list);
+		parse_commit(commit);
+		parents = commit->parents;
+
+		commit->object.flags |= POPPED;
+		if (!(commit->object.flags & COMMON))
+			data->non_common_revs--;
+
+		if (commit->object.flags & COMMON) {
+			/* do not send "have", and ignore ancestors */
+			commit = NULL;
+			mark = COMMON | SEEN;
+		} else if (commit->object.flags & COMMON_REF)
+			/* send "have", and ignore ancestors */
+			mark = COMMON | SEEN;
+		else
+			/* send "have", also for its ancestors */
+			mark = SEEN;
+
+		while (parents) {
+			if (!(parents->item->object.flags & SEEN))
+				rev_list_push(data, parents->item, mark);
+			if (mark & COMMON)
+				mark_common(data, parents->item, 1, 0);
+			parents = parents->next;
+		}
+	}
+
+	return &commit->object.oid;
+}
+
+static void known_common(struct fetch_negotiator *n, struct commit *c)
+{
+	if (!(c->object.flags & SEEN)) {
+		rev_list_push(n->data, c, COMMON_REF | SEEN);
+		mark_common(n->data, c, 1, 1);
+	}
+}
+
+static void add_tip(struct fetch_negotiator *n, struct commit *c)
+{
+	n->known_common = NULL;
+	rev_list_push(n->data, c, SEEN);
+}
+
+static const struct object_id *next(struct fetch_negotiator *n)
+{
+	n->known_common = NULL;
+	n->add_tip = NULL;
+	return get_rev(n->data);
+}
+
+static int ack(struct fetch_negotiator *n, struct commit *c)
+{
+	int known_to_be_common = !!(c->object.flags & COMMON);
+	mark_common(n->data, c, 0, 1);
+	return known_to_be_common;
+}
+
+static void release(struct fetch_negotiator *n)
+{
+	clear_prio_queue(&((struct data *)n->data)->rev_list);
+	FREE_AND_NULL(n->data);
+}
+
+void default_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	struct data *data;
+	negotiator->known_common = known_common;
+	negotiator->add_tip = add_tip;
+	negotiator->next = next;
+	negotiator->ack = ack;
+	negotiator->release = release;
+	negotiator->data = data = xcalloc(1, sizeof(*data));
+	data->rev_list.compare = compare_commits_by_commit_date;
+
+	if (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
+}
diff --git a/negotiator/default.h b/negotiator/default.h
new file mode 100644
index 000000000..6c4b7e526
--- /dev/null
+++ b/negotiator/default.h
@@ -0,0 +1,8 @@
+#ifndef NEGOTIATOR_DEFAULT_H
+#define NEGOTIATOR_DEFAULT_H
+
+#include "fetch-negotiator.h"
+
+void default_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/object.h b/object.h
index 5c1395500..7db4941d6 100644
--- a/object.h
+++ b/object.h
@@ -28,7 +28,8 @@ struct object_array {
 /*
  * object flag allocation:
  * revision.h:               0---------10                                26
- * fetch-pack.c:             0----5
+ * fetch-pack.c:             01
+ * negotiator/default.c:       2--5
  * walker.c:                 0-2
  * upload-pack.c:                4       11----------------19
  * builtin/blame.c:                        12-13
-- 
2.17.0.768.g1526ddbba1.dirty

Re: [PATCH 1/6] fetch-pack: clear marks before everything_local()

[Jonathan Nieder]

Hi,

Jonathan Tan wrote:

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

[...]
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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);
> @@ -1053,6 +1050,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 (marked)
> +		for_each_ref(clear_marks, NULL);
> +	marked = 1;
>  	if (everything_local(args, &ref, sought, nr_sought)) {

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?

Thanks,
Jonathan

Re: [PATCH 2/6] fetch-pack: truly stop negotiation upon ACK ready

[Jonathan Nieder]

Hi,

Jonathan Tan wrote:

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

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

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

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.

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

> 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 <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
[...]
> +++ b/fetch-pack.c
> @@ -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;

Makes sense.

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

Thanks,
Jonathan

Re: [PATCH 2/6] fetch-pack: truly stop negotiation upon ACK ready

[Jonathan Nieder]

Jonathan Nieder wrote:
> Jonathan Tan wrote:

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

Whoops.  My spellchecker deceived me.

I even checked Wiktionary and found that it was a verb there and didn't
bother to look at the definition:

	Misspelling of proceed

You already had the right spelling.

Sorry for the noise,
Jonathan

Re: [PATCH 3/6] fetch-pack: in protocol v2, enqueue commons first

[Jonathan Nieder]

Hi,

Jonathan Tan wrote:

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

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. :)

[...]
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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);
> -			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))
>  				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);

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?

>  			break;
>  		case FETCH_SEND_REQUEST:
>  			if (send_fetch_request(fd[1], args, ref, &common,
> diff --git a/t/t5500-fetch-pack.sh b/t/t5500-fetch-pack.sh
> index 0680dec80..ad6a50ad6 100755
> --- a/t/t5500-fetch-pack.sh
> +++ b/t/t5500-fetch-pack.sh
> @@ -808,6 +808,41 @@ test_expect_success 'fetch with --filter=blob:limit=0' '
>  	fetch_filter_blob_limit_zero server server
>  '
>  
> +test_expect_success 'use ref advertisement to prune "have" lines sent' '

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.

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

> +
> +	# 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]

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

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

> +	! grep "have $(git -C client rev-parse aref_both_2^)" trace &&

Nice.

Thanks for a pleasant read,
Jonathan

Re: [PATCH 4/6] fetch-pack: make negotiation-related vars local

[Jonathan Nieder]

Jonathan Tan wrote:

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

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

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.

[...]
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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;
> +};

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

The rest looks good.

Thanks,
Jonathan

Re: [PATCH 5/6] fetch-pack: move common check and marking together

[Jonathan Nieder]

Hi,

Jonathan Tan wrote:

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

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.

> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)

With or without such a clarification,
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

Thanks.

Re: [PATCH 1/6] fetch-pack: clear marks before everything_local()

[Jonathan Tan]

On Tue, 5 Jun 2018 16:08:21 -0700
Jonathan Nieder <jrnieder@gmail.com> wrote:

> Hi,
> 
> Jonathan Tan wrote:
> 
> > 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?

Firstly, I don't know of a practical way to demonstrate this, because we
don't have an implementation of a transport that does not support tag
following. If we could demonstrate this, I think we can demonstrating it
by constructing a negotiation scenario in which COMMON_REF would have
been helpful, e.g. the following (untested) scenario:

 T C (T=tag, C=commit)
 |/
 O

We run "git fetch C" and on the second round (when we fetch T), if we
wiped the flags *after* everything_local() (as is currently done),
negotiation would send "have C" and "have O". But if we wiped the flags
*before* everything_local(), then C would have the COMMON_REF flag and
we will see that we only send "have C". So we have more efficient
negotiation.

> 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. :/

Yes, because we don't have tests against a transport which doesn't
support tag following.

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

One idea is to first separate everything_local() into its side effect
parts and the "true" check that everything is local. I'll do that and
send it as part of v2 of this patch series.

Re: [PATCH 6/6] fetch-pack: introduce negotiator API

[Jonathan Nieder]

Jonathan Tan wrote:

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

nit: s/more//

> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  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

Looks like a job for --color-moved. :)

[...]
> --- /dev/null
> +++ b/fetch-negotiator.c
> @@ -0,0 +1,7 @@
> +#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.

[...]
> +++ b/fetch-negotiator.h
> @@ -0,0 +1,45 @@
> +#ifndef FETCH_NEGOTIATOR
> +#define FETCH_NEGOTIATOR
> +
> +#include "cache.h"

What does this need from cache.h?

> +#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?

[...]
> +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.

[...]
> +++ b/object.h
> @@ -28,7 +28,8 @@ struct object_array {
>  /*
>   * object flag allocation:
>   * revision.h:               0---------10                                26
> - * fetch-pack.c:             0----5
> + * fetch-pack.c:             01
> + * negotiator/default.c:       2--5
>   * walker.c:                 0-2

Nice!

[...]
> +++ b/fetch-pack.c
[...]
> @@ -462,7 +348,7 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
>  	retval = -1;
>  	if (args->no_dependents)
>  		goto done;
> -	while ((oid = get_rev(data))) {
> +	while ((oid = negotiator->next(negotiator))) {
[etc]

I like it. :)

[...]
> @@ -988,7 +870,8 @@ 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 } };
> +	struct fetch_negotiator negotiator;
> +	fetch_negotiator_init(&negotiator);

Sane.

[...]
> @@ -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)
>  			/* 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?

[...]
> @@ -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).

[...]
> +++ b/negotiator/default.c
> @@ -0,0 +1,173 @@
> +#include "default.h"

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

[...]
> +/*
> +   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).

[...]
> --- /dev/null
> +++ b/negotiator/default.h
> @@ -0,0 +1,8 @@
> +#ifndef NEGOTIATOR_DEFAULT_H
> +#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.

Except where noted above,
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

Thanks for a nice cleanup.

Re: [PATCH 2/6] fetch-pack: truly stop negotiation upon ACK ready

[Jonathan Tan]

On Tue, 5 Jun 2018 16:16:34 -0700
Jonathan Nieder <jrnieder@gmail.com> wrote:

> Hi,
> 
> Jonathan Tan wrote:
> 
> > 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"?

"Appears to work" means I think that it works, but I don't think I can
conclusively prove it.

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

I tried to figure out which, but concluded that I can't.

I think that in v2's commit message, I'll start with describing the
readability aspect.

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

No (which potentially causes a problem in the case that fetch-pack is
invoked twice), but I fix that in patch 4/6, so I didn't bother
addressing it here. I'll add a note about the lifetime of this priority
queue in v2.

Re: [PATCH 3/6] fetch-pack: in protocol v2, enqueue commons first

[Jonathan Tan]

On Tue, Jun 5, 2018 at 4:30 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> 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. :)

OK, I'll start the commit message with explaining a situation in which
these redundant "have" lines will appear instead. (The situation will
be the same as the one in the test.)

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

You're right that there's a side effect in everything_local. In v2,
I'll have a preparatory patch to separate it into a few functions so
that we can see what happens more clearly.

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

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

"A ref", "a" as in "one". I'll find a better name (probably just
"both_1" and "both_2").

>> +
>> +     # 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]

Thanks - I'll use your suggestion.

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

The server's ref advertisement makes it redundant. I'll explain this
more clearly in v2.

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

Will do. Thanks for your comments.

Re: [PATCH 4/6] fetch-pack: make negotiation-related vars local

[Jonathan Tan]

On Tue, Jun 5, 2018 at 4:35 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Jonathan Tan wrote:
>
>> 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/
>
>> 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.
>
> Hm.  Is the idea that 'struct data' gets stored in the opaque 'data'
> member of the fetch_negotiator?

Yes.

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

I wanted to make it easier to review the subsequent patch, in that
entire functions, including the signature, can be moved verbatim. If
the project prefers that I don't do that, let me know.

> [...]
>> --- a/fetch-pack.c
>> +++ b/fetch-pack.c
>> @@ -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;
>> +};
>
> How does this struct get used?  What does it represent?  A comment
> might help.

I'll add a comment.

Re: [PATCH 5/6] fetch-pack: move common check and marking together

[Jonathan Tan]

On Tue, Jun 5, 2018 at 5:01 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> 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.

Thanks, I'll use your suggestion.

Re: [PATCH 6/6] fetch-pack: introduce negotiator API

[Jonathan Tan]

On Tue, Jun 5, 2018 at 5:37 PM, Jonathan Nieder <jrnieder@gmail.com> wrote:
>> 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//

OK.

>> +#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.

OK.

>> +#include "cache.h"
>
> What does this need from cache.h?

If I remember correctly, I needed something, but I might not. I'll
remove it if so.

>> +#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?

I'll use the forward declaration then.

> [...]
>> +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.

OK.

>> @@ -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)
>>                       /* 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?

Good point - will do.

>> @@ -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).

OK.

>> +++ b/negotiator/default.c
>> @@ -0,0 +1,173 @@
>> +#include "default.h"
>
> First #include should be "git-compat-util.h".

OK.

> [...]
>> +/*
>> +   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.

>> --- /dev/null
>> +++ b/negotiator/default.h
>> @@ -0,0 +1,8 @@
>> +#ifndef NEGOTIATOR_DEFAULT_H
>> +#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.

I'll use a forward declaration.

[PATCH v2 0/8] Refactor fetch negotiation into its own API

[Jonathan Tan]

Thanks, Jonathan Nieder, for your comments.

This patch set now includes a patch at the beginning to split up
everything_local(), making it clear which functions have side effects
and which don't, and a patch at the end to reformat some comments.

While I was implementing the suggestions, there were some that I were
unsure about. Here they are:

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

I couldn't find a logical place (I didn't see any existing tests that
test negotiation). I did move it up a bit earlier in the file, before
filtering by blob size, because that seemed more distinct from the rest
of the tests.

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

I thought of adding a comment, but felt that I would end up removing it
anyway upon its move to negotiator/default.c, so I didn't end up adding
it.

> >> +/*
> >> +   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.

I'm now not sure of the value of making a change just to update
formatting, but I added the followup commit anyway - it can be easily
dropped if we decide to do so.

Jonathan Tan (8):
  fetch-pack: split up everything_local()
  fetch-pack: clear marks before re-marking
  fetch-pack: directly end negotiation if ACK ready
  fetch-pack: use ref adv. to prune "have" sent
  fetch-pack: make negotiation-related vars local
  fetch-pack: move common check and marking together
  fetch-pack: introduce negotiator API
  negotiator/default: use better style in comments

 Makefile              |   2 +
 fetch-negotiator.c    |   8 ++
 fetch-negotiator.h    |  57 ++++++++++
 fetch-pack.c          | 254 ++++++++++++++----------------------------
 negotiator/default.c  | 174 +++++++++++++++++++++++++++++
 negotiator/default.h  |   8 ++
 object.h              |   3 +-
 t/t5500-fetch-pack.sh |  39 +++++++
 8 files changed, 376 insertions(+), 169 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

-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 1/8] fetch-pack: split up everything_local()

[Jonathan Tan]

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 <jonathantanmy@google.com>
---
 fetch-pack.c | 39 ++++++++++++++++++++++++++++++---------
 1 file changed, 30 insertions(+), 9 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index a320ce987..5c87bb8bb 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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;
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 2/8] fetch-pack: clear marks before re-marking

[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 invocation of
mark_complete_and_common_ref() in do_fetch_pack() is useless.

(This cannot be reproduced with Git alone, because all transports that
come with Git support tag following.)

Therefore, move this clearing from find_common() to its
parent function do_fetch_pack(), right before it calls
mark_complete_and_common_ref().

This has been occurring since the commit that introduced the clearing of
marks, 420e9af498 ("Fix tag following", 2008-03-19).

The corresponding code for protocol v2 in do_fetch_pack_v2() does not
have this problem, as the clearing of flags is done before any marking
(whether by rev_list_insert_ref_oid() or
mark_complete_and_common_ref()).

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 fetch-pack.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 5c87bb8bb..2812499a5 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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);
@@ -1070,6 +1067,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 (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
 	mark_complete_and_common_ref(args, &ref);
 	filter_refs(args, &ref, sought, nr_sought);
 	if (everything_local(args, &ref)) {
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 3/8] fetch-pack: directly end negotiation if ACK ready

[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
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 <jonathantanmy@google.com>
---
 fetch-pack.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 2812499a5..09f5c83c4 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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;
 		}
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 4/8] fetch-pack: use ref adv. to prune "have" sent

[Jonathan Tan]

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 <jonathantanmy@google.com>
---
 fetch-pack.c          |  6 +++---
 t/t5500-fetch-pack.sh | 39 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 42 insertions(+), 3 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 09f5c83c4..114207b8e 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -1391,9 +1391,6 @@ 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);
-			for_each_cached_alternate(insert_one_alternate_object);
-
 			/* Filter 'ref' by 'sought' and those that aren't local */
 			mark_complete_and_common_ref(args, &ref);
 			filter_refs(args, &ref, sought, nr_sought);
@@ -1401,6 +1398,9 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 				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);
 			break;
 		case FETCH_SEND_REQUEST:
 			if (send_fetch_request(fd[1], args, ref, &common,
diff --git a/t/t5500-fetch-pack.sh b/t/t5500-fetch-pack.sh
index d4f435155..026ba9c9e 100755
--- a/t/t5500-fetch-pack.sh
+++ b/t/t5500-fetch-pack.sh
@@ -755,6 +755,45 @@ test_expect_success 'fetching deepen' '
 	)
 '
 
+test_expect_success 'use ref advertisement to prune "have" lines sent' '
+	rm -rf server client &&
+	git init server &&
+	test_commit -C server both_have_1 &&
+	git -C server tag -d both_have_1 &&
+	test_commit -C server both_have_2 &&
+
+	# In this test, the ref name that only the server has is a prefix of all
+	# other refs. This is because in protocol v2, the client sends
+	# "ref-prefix" to limit the ref advertisement. Naming the ref "bo" means
+	# that "ref-prefix refs/tags/bo*" is sent, resulting in the client also
+	# knowing about refs/tags/both_have_2, just as it would when it uses
+	# protocol v0.
+	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 &&
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 5/8] fetch-pack: make negotiation-related vars local

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

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 <jonathantanmy@google.com>
---
 fetch-pack.c | 104 +++++++++++++++++++++++++++++----------------------
 1 file changed, 59 insertions(+), 45 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 114207b8e..c31644bb9 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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;
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 6/8] fetch-pack: move common check and marking together

[Jonathan Tan]

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.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 fetch-pack.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index c31644bb9..4a4ec4da3 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -499,11 +499,14 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 				case ACK_continue: {
 					struct commit *commit =
 						lookup_commit(result_oid);
+					int was_common;
 					if (!commit)
 						die(_("invalid commit %s"), oid_to_hex(result_oid));
+					was_common = commit->object.flags & COMMON;
+					mark_common(data, commit, 0, 1);
 					if (args->stateless_rpc
 					 && ack == ACK_common
-					 && !(commit->object.flags & COMMON)) {
+					 && !was_common) {
 						/* We need to replay the have for this object
 						 * on the next RPC request so the peer knows
 						 * it is in common with us.
@@ -520,7 +523,6 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 					} else if (!args->stateless_rpc
 						   || ack != ACK_common)
 						in_vain = 0;
-					mark_common(data, commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
 					if (ack == ACK_ready)
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 7/8] fetch-pack: introduce negotiator API

[Jonathan Tan]

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 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 <jonathantanmy@google.com>
---
 Makefile             |   2 +
 fetch-negotiator.c   |   8 ++
 fetch-negotiator.h   |  57 ++++++++++++
 fetch-pack.c         | 206 +++++++++----------------------------------
 negotiator/default.c | 176 ++++++++++++++++++++++++++++++++++++
 negotiator/default.h |   8 ++
 object.h             |   3 +-
 7 files changed, 297 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

diff --git a/Makefile b/Makefile
index 1d27f3636..96f84d1dc 100644
--- a/Makefile
+++ b/Makefile
@@ -859,6 +859,7 @@ LIB_OBJS += ewah/ewah_bitmap.o
 LIB_OBJS += ewah/ewah_io.o
 LIB_OBJS += ewah/ewah_rlw.o
 LIB_OBJS += exec-cmd.o
+LIB_OBJS += fetch-negotiator.o
 LIB_OBJS += fetch-object.o
 LIB_OBJS += fetch-pack.o
 LIB_OBJS += fsck.o
@@ -891,6 +892,7 @@ LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
 LIB_OBJS += name-hash.o
+LIB_OBJS += negotiator/default.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
diff --git a/fetch-negotiator.c b/fetch-negotiator.c
new file mode 100644
index 000000000..2675d120f
--- /dev/null
+++ b/fetch-negotiator.c
@@ -0,0 +1,8 @@
+#include "git-compat-util.h"
+#include "fetch-negotiator.h"
+#include "negotiator/default.h"
+
+void fetch_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	default_negotiator_init(negotiator);
+}
diff --git a/fetch-negotiator.h b/fetch-negotiator.h
new file mode 100644
index 000000000..b1290aa9c
--- /dev/null
+++ b/fetch-negotiator.h
@@ -0,0 +1,57 @@
+#ifndef FETCH_NEGOTIATOR
+#define FETCH_NEGOTIATOR
+
+struct commit;
+
+/*
+ * An object that supplies the information needed to negotiate the contents of
+ * the to-be-sent packfile during a fetch.
+ *
+ * To set up the negotiator, call fetch_negotiator_init(), then known_common()
+ * (0 or more times), then add_tip() (0 or more times).
+ *
+ * Then, when "have" lines are required, call next(). Call ack() to report what
+ * the server tells us.
+ *
+ * Once negotiation is done, call release(). The negotiator then cannot be used
+ * (unless reinitialized with fetch_negotiator_init()).
+ */
+struct fetch_negotiator {
+	/*
+	 * Before negotiation starts, indicate that the server is known to have
+	 * this commit.
+	 */
+	void (*known_common)(struct fetch_negotiator *, struct commit *);
+
+	/*
+	 * Once this function is invoked, known_common() cannot be invoked any
+	 * more.
+	 *
+	 * Indicate that this commit and all its ancestors are to be checked
+	 * for commonality with the server.
+	 */
+	void (*add_tip)(struct fetch_negotiator *, struct commit *);
+
+	/*
+	 * Once this function is invoked, known_common() and add_tip() cannot
+	 * be invoked any more.
+	 *
+	 * Return the next commit that the client should send as a "have" line.
+	 */
+	const struct object_id *(*next)(struct fetch_negotiator *);
+
+	/*
+	 * Inform the negotiator that the server has the given commit. This
+	 * method must only be called on commits returned by next().
+	 */
+	int (*ack)(struct fetch_negotiator *, struct commit *);
+
+	void (*release)(struct fetch_negotiator *);
+
+	/* internal use */
+	void *data;
+};
+
+void fetch_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/fetch-pack.c b/fetch-pack.c
index 4a4ec4da3..ad6f7ac32 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -15,10 +15,10 @@
 #include "connect.h"
 #include "transport.h"
 #include "version.h"
-#include "prio-queue.h"
 #include "sha1-array.h"
 #include "oidset.h"
 #include "packfile.h"
+#include "fetch-negotiator.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -36,13 +36,7 @@ static const char *alternate_shallow_file;
 
 /* Remember to update object flag allocation in object.h */
 #define COMPLETE	(1U << 0)
-#define COMMON		(1U << 1)
-#define COMMON_REF	(1U << 2)
-#define SEEN		(1U << 3)
-#define POPPED		(1U << 4)
-#define ALTERNATE	(1U << 5)
-
-static int marked;
+#define ALTERNATE	(1U << 1)
 
 /*
  * After sending this many "have"s if we do not get any new ACK , we
@@ -50,11 +44,6 @@ static int marked;
  */
 #define MAX_IN_VAIN 256
 
-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
@@ -97,8 +86,8 @@ static void cache_one_alternate(const char *refname,
 	cache->items[cache->nr++] = obj;
 }
 
-static void for_each_cached_alternate(struct data *data,
-				      void (*cb)(struct data *, struct object *))
+static void for_each_cached_alternate(struct fetch_negotiator *negotiator,
+				      void (*cb)(struct fetch_negotiator *, struct object *))
 {
 	static int initialized;
 	static struct alternate_object_cache cache;
@@ -110,31 +99,17 @@ static void for_each_cached_alternate(struct data *data,
 	}
 
 	for (i = 0; i < cache.nr; i++)
-		cb(data, cache.items[i]);
-}
-
-static void rev_list_push(struct data *data, struct commit *commit, int mark)
-{
-	if (!(commit->object.flags & mark)) {
-		commit->object.flags |= mark;
-
-		if (parse_commit(commit))
-			return;
-
-		prio_queue_put(&data->rev_list, commit);
-
-		if (!(commit->object.flags & COMMON))
-			data->non_common_revs++;
-	}
+		cb(negotiator, cache.items[i]);
 }
 
-static int rev_list_insert_ref(struct data *data, const char *refname,
+static int rev_list_insert_ref(struct fetch_negotiator *negotiator,
+			       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(data, (struct commit *)o, SEEN);
+		negotiator->add_tip(negotiator, (struct commit *)o);
 
 	return 0;
 }
@@ -145,97 +120,6 @@ static int rev_list_insert_ref_oid(const char *refname, const struct object_id *
 	return rev_list_insert_ref(cb_data, refname, oid);
 }
 
-static int clear_marks(const char *refname, const struct object_id *oid,
-		       int flag, void *cb_data)
-{
-	struct object *o = deref_tag(parse_object(oid), refname, 0);
-
-	if (o && o->type == OBJ_COMMIT)
-		clear_commit_marks((struct commit *)o,
-				   COMMON | COMMON_REF | SEEN | POPPED);
-	return 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).
-*/
-
-static void mark_common(struct data *data, struct commit *commit,
-		int ancestors_only, int dont_parse)
-{
-	if (commit != NULL && !(commit->object.flags & COMMON)) {
-		struct object *o = (struct object *)commit;
-
-		if (!ancestors_only)
-			o->flags |= COMMON;
-
-		if (!(o->flags & SEEN))
-			rev_list_push(data, commit, SEEN);
-		else {
-			struct commit_list *parents;
-
-			if (!ancestors_only && !(o->flags & POPPED))
-				data->non_common_revs--;
-			if (!o->parsed && !dont_parse)
-				if (parse_commit(commit))
-					return;
-
-			for (parents = commit->parents;
-					parents;
-					parents = parents->next)
-				mark_common(data, parents->item, 0, dont_parse);
-		}
-	}
-}
-
-/*
-  Get the next rev to send, ignoring the common.
-*/
-
-static const struct object_id *get_rev(struct data *data)
-{
-	struct commit *commit = NULL;
-
-	while (commit == NULL) {
-		unsigned int mark;
-		struct commit_list *parents;
-
-		if (data->rev_list.nr == 0 || data->non_common_revs == 0)
-			return NULL;
-
-		commit = prio_queue_get(&data->rev_list);
-		parse_commit(commit);
-		parents = commit->parents;
-
-		commit->object.flags |= POPPED;
-		if (!(commit->object.flags & COMMON))
-			data->non_common_revs--;
-
-		if (commit->object.flags & COMMON) {
-			/* do not send "have", and ignore ancestors */
-			commit = NULL;
-			mark = COMMON | SEEN;
-		} else if (commit->object.flags & COMMON_REF)
-			/* send "have", and ignore ancestors */
-			mark = COMMON | SEEN;
-		else
-			/* send "have", also for its ancestors */
-			mark = SEEN;
-
-		while (parents) {
-			if (!(parents->item->object.flags & SEEN))
-				rev_list_push(data, parents->item, mark);
-			if (mark & COMMON)
-				mark_common(data, parents->item, 1, 0);
-			parents = parents->next;
-		}
-	}
-
-	return &commit->object.oid;
-}
-
 enum ack_type {
 	NAK = 0,
 	ACK,
@@ -302,9 +186,10 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_object(struct data *data, struct object *obj)
+static void insert_one_alternate_object(struct fetch_negotiator *negotiator,
+					struct object *obj)
 {
-	rev_list_insert_ref(data, NULL, &obj->oid);
+	rev_list_insert_ref(negotiator, NULL, &obj->oid);
 }
 
 #define INITIAL_FLUSH 16
@@ -327,7 +212,8 @@ static int next_flush(int stateless_rpc, int count)
 	return count;
 }
 
-static int find_common(struct data *data, struct fetch_pack_args *args,
+static int find_common(struct fetch_negotiator *negotiator,
+		       struct fetch_pack_args *args,
 		       int fd[2], struct object_id *result_oid,
 		       struct ref *refs)
 {
@@ -343,8 +229,8 @@ static int find_common(struct data *data, 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, data);
-	for_each_cached_alternate(data, insert_one_alternate_object);
+	for_each_ref(rev_list_insert_ref_oid, negotiator);
+	for_each_cached_alternate(negotiator, insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
@@ -462,7 +348,7 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 	retval = -1;
 	if (args->no_dependents)
 		goto done;
-	while ((oid = get_rev(data))) {
+	while ((oid = negotiator->next(negotiator))) {
 		packet_buf_write(&req_buf, "have %s\n", oid_to_hex(oid));
 		print_verbose(args, "have %s", oid_to_hex(oid));
 		in_vain++;
@@ -502,8 +388,7 @@ static int find_common(struct data *data, struct fetch_pack_args *args,
 					int was_common;
 					if (!commit)
 						die(_("invalid commit %s"), oid_to_hex(result_oid));
-					was_common = commit->object.flags & COMMON;
-					mark_common(data, commit, 0, 1);
+					was_common = negotiator->ack(negotiator, commit);
 					if (args->stateless_rpc
 					 && ack == ACK_common
 					 && !was_common) {
@@ -712,7 +597,8 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(struct data *unused, struct object *obj)
+static void mark_alternate_complete(struct fetch_negotiator *unused,
+				    struct object *obj)
 {
 	mark_complete(&obj->oid);
 }
@@ -749,7 +635,7 @@ 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 data *data,
+static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator,
 					 struct fetch_pack_args *args,
 					 struct ref **refs)
 {
@@ -818,12 +704,8 @@ static void mark_complete_and_common_ref(struct data *data,
 			if (!o || o->type != OBJ_COMMIT || !(o->flags & COMPLETE))
 				continue;
 
-			if (!(o->flags & SEEN)) {
-				rev_list_push(data, (struct commit *)o,
-					      COMMON_REF | SEEN);
-
-				mark_common(data, (struct commit *)o, 1, 1);
-			}
+			negotiator->known_common(negotiator,
+						 (struct commit *)o);
 		}
 	}
 
@@ -1005,7 +887,8 @@ 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 } };
+	struct fetch_negotiator negotiator;
+	fetch_negotiator_init(&negotiator);
 
 	sort_ref_list(&ref, ref_compare_name);
 	QSORT(sought, nr_sought, cmp_ref_by_name);
@@ -1078,16 +961,13 @@ 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;
-	mark_complete_and_common_ref(&data, args, &ref);
+	mark_complete_and_common_ref(&negotiator, args, &ref);
 	filter_refs(args, &ref, sought, nr_sought);
 	if (everything_local(args, &ref)) {
 		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)
 			/* When cloning, it is not unusual to have
 			 * no common commit.
@@ -1107,6 +987,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 		die(_("git fetch-pack: fetch failed."));
 
  all_done:
+	negotiator.release(&negotiator);
 	return ref;
 }
 
@@ -1168,14 +1049,15 @@ static void add_common(struct strbuf *req_buf, struct oidset *common)
 	}
 }
 
-static int add_haves(struct data *data, struct strbuf *req_buf,
+static int add_haves(struct fetch_negotiator *negotiator,
+		     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(data))) {
+	while ((oid = negotiator->next(negotiator))) {
 		packet_buf_write(req_buf, "have %s\n", oid_to_hex(oid));
 		if (++haves_added >= *haves_to_send)
 			break;
@@ -1194,7 +1076,7 @@ static int add_haves(struct data *data, struct strbuf *req_buf,
 	return ret;
 }
 
-static int send_fetch_request(struct data *data, int fd_out,
+static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,
 			      const struct fetch_pack_args *args,
 			      const struct ref *wants, struct oidset *common,
 			      int *haves_to_send, int *in_vain)
@@ -1251,7 +1133,7 @@ static int send_fetch_request(struct data *data, int fd_out,
 		add_common(&req_buf, common);
 
 		/* Add initial haves */
-		ret = add_haves(data, &req_buf, haves_to_send, in_vain);
+		ret = add_haves(negotiator, &req_buf, haves_to_send, in_vain);
 	}
 
 	/* Send request */
@@ -1288,7 +1170,8 @@ static int process_section_header(struct packet_reader *reader,
 	return ret;
 }
 
-static int process_acks(struct data *data, struct packet_reader *reader,
+static int process_acks(struct fetch_negotiator *negotiator,
+			struct packet_reader *reader,
 			struct oidset *common)
 {
 	/* received */
@@ -1308,7 +1191,7 @@ static int process_acks(struct data *data, struct packet_reader *reader,
 				struct commit *commit;
 				oidset_insert(common, &oid);
 				commit = lookup_commit(&oid);
-				mark_common(data, commit, 0, 1);
+				negotiator->ack(negotiator, commit);
 			}
 			continue;
 		}
@@ -1386,7 +1269,8 @@ 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 } };
+	struct fetch_negotiator negotiator;
+	fetch_negotiator_init(&negotiator);
 	packet_reader_init(&reader, fd[0], NULL, 0,
 			   PACKET_READ_CHOMP_NEWLINE);
 
@@ -1402,24 +1286,21 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			if (args->depth > 0 || args->deepen_since || args->deepen_not)
 				args->deepen = 1;
 
-			if (marked)
-				for_each_ref(clear_marks, NULL);
-			marked = 1;
-
 			/* Filter 'ref' by 'sought' and those that aren't local */
-			mark_complete_and_common_ref(&data, args, &ref);
+			mark_complete_and_common_ref(&negotiator, 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, &data);
-			for_each_cached_alternate(&data,
+			for_each_ref(rev_list_insert_ref_oid, &negotiator);
+			for_each_cached_alternate(&negotiator,
 						  insert_one_alternate_object);
 			break;
 		case FETCH_SEND_REQUEST:
-			if (send_fetch_request(&data, fd[1], args, ref, &common,
+			if (send_fetch_request(&negotiator, fd[1], args, ref,
+					       &common,
 					       &haves_to_send, &in_vain))
 				state = FETCH_GET_PACK;
 			else
@@ -1427,7 +1308,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			break;
 		case FETCH_PROCESS_ACKS:
 			/* Process ACKs/NAKs */
-			switch (process_acks(&data, &reader, &common)) {
+			switch (process_acks(&negotiator, &reader, &common)) {
 			case 2:
 				state = FETCH_GET_PACK;
 				break;
@@ -1456,6 +1337,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 		}
 	}
 
+	negotiator.release(&negotiator);
 	oidset_clear(&common);
 	return ref;
 }
diff --git a/negotiator/default.c b/negotiator/default.c
new file mode 100644
index 000000000..b8f45cf78
--- /dev/null
+++ b/negotiator/default.c
@@ -0,0 +1,176 @@
+#include "cache.h"
+#include "default.h"
+#include "../commit.h"
+#include "../fetch-negotiator.h"
+#include "../prio-queue.h"
+#include "../refs.h"
+#include "../tag.h"
+
+/* Remember to update object flag allocation in object.h */
+#define COMMON		(1U << 2)
+#define COMMON_REF	(1U << 3)
+#define SEEN		(1U << 4)
+#define POPPED		(1U << 5)
+
+static int marked;
+
+struct data {
+	struct prio_queue rev_list;
+	int non_common_revs;
+};
+
+static void rev_list_push(struct data *data, struct commit *commit, int mark)
+{
+	if (!(commit->object.flags & mark)) {
+		commit->object.flags |= mark;
+
+		if (parse_commit(commit))
+			return;
+
+		prio_queue_put(&data->rev_list, commit);
+
+		if (!(commit->object.flags & COMMON))
+			data->non_common_revs++;
+	}
+}
+
+static int clear_marks(const char *refname, const struct object_id *oid,
+		       int flag, void *cb_data)
+{
+	struct object *o = deref_tag(parse_object(oid), refname, 0);
+
+	if (o && o->type == OBJ_COMMIT)
+		clear_commit_marks((struct commit *)o,
+				   COMMON | COMMON_REF | SEEN | POPPED);
+	return 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).
+*/
+
+static void mark_common(struct data *data, struct commit *commit,
+		int ancestors_only, int dont_parse)
+{
+	if (commit != NULL && !(commit->object.flags & COMMON)) {
+		struct object *o = (struct object *)commit;
+
+		if (!ancestors_only)
+			o->flags |= COMMON;
+
+		if (!(o->flags & SEEN))
+			rev_list_push(data, commit, SEEN);
+		else {
+			struct commit_list *parents;
+
+			if (!ancestors_only && !(o->flags & POPPED))
+				data->non_common_revs--;
+			if (!o->parsed && !dont_parse)
+				if (parse_commit(commit))
+					return;
+
+			for (parents = commit->parents;
+					parents;
+					parents = parents->next)
+				mark_common(data, parents->item, 0, dont_parse);
+		}
+	}
+}
+
+/*
+  Get the next rev to send, ignoring the common.
+*/
+
+static const struct object_id *get_rev(struct data *data)
+{
+	struct commit *commit = NULL;
+
+	while (commit == NULL) {
+		unsigned int mark;
+		struct commit_list *parents;
+
+		if (data->rev_list.nr == 0 || data->non_common_revs == 0)
+			return NULL;
+
+		commit = prio_queue_get(&data->rev_list);
+		parse_commit(commit);
+		parents = commit->parents;
+
+		commit->object.flags |= POPPED;
+		if (!(commit->object.flags & COMMON))
+			data->non_common_revs--;
+
+		if (commit->object.flags & COMMON) {
+			/* do not send "have", and ignore ancestors */
+			commit = NULL;
+			mark = COMMON | SEEN;
+		} else if (commit->object.flags & COMMON_REF)
+			/* send "have", and ignore ancestors */
+			mark = COMMON | SEEN;
+		else
+			/* send "have", also for its ancestors */
+			mark = SEEN;
+
+		while (parents) {
+			if (!(parents->item->object.flags & SEEN))
+				rev_list_push(data, parents->item, mark);
+			if (mark & COMMON)
+				mark_common(data, parents->item, 1, 0);
+			parents = parents->next;
+		}
+	}
+
+	return &commit->object.oid;
+}
+
+static void known_common(struct fetch_negotiator *n, struct commit *c)
+{
+	if (!(c->object.flags & SEEN)) {
+		rev_list_push(n->data, c, COMMON_REF | SEEN);
+		mark_common(n->data, c, 1, 1);
+	}
+}
+
+static void add_tip(struct fetch_negotiator *n, struct commit *c)
+{
+	n->known_common = NULL;
+	rev_list_push(n->data, c, SEEN);
+}
+
+static const struct object_id *next(struct fetch_negotiator *n)
+{
+	n->known_common = NULL;
+	n->add_tip = NULL;
+	return get_rev(n->data);
+}
+
+static int ack(struct fetch_negotiator *n, struct commit *c)
+{
+	int known_to_be_common = !!(c->object.flags & COMMON);
+	mark_common(n->data, c, 0, 1);
+	return known_to_be_common;
+}
+
+static void release(struct fetch_negotiator *n)
+{
+	clear_prio_queue(&((struct data *)n->data)->rev_list);
+	FREE_AND_NULL(n->data);
+}
+
+void default_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	struct data *data;
+	negotiator->known_common = known_common;
+	negotiator->add_tip = add_tip;
+	negotiator->next = next;
+	negotiator->ack = ack;
+	negotiator->release = release;
+	negotiator->data = data = xcalloc(1, sizeof(*data));
+	data->rev_list.compare = compare_commits_by_commit_date;
+
+	if (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
+}
diff --git a/negotiator/default.h b/negotiator/default.h
new file mode 100644
index 000000000..d23a8f2fb
--- /dev/null
+++ b/negotiator/default.h
@@ -0,0 +1,8 @@
+#ifndef NEGOTIATOR_DEFAULT_H
+#define NEGOTIATOR_DEFAULT_H
+
+struct fetch_negotiator;
+
+void default_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/object.h b/object.h
index 5c1395500..7db4941d6 100644
--- a/object.h
+++ b/object.h
@@ -28,7 +28,8 @@ struct object_array {
 /*
  * object flag allocation:
  * revision.h:               0---------10                                26
- * fetch-pack.c:             0----5
+ * fetch-pack.c:             01
+ * negotiator/default.c:       2--5
  * walker.c:                 0-2
  * upload-pack.c:                4       11----------------19
  * builtin/blame.c:                        12-13
-- 
2.17.0.768.g1526ddbba1.dirty

[PATCH v2 8/8] negotiator/default: use better style in comments

[Jonathan Tan]

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 negotiator/default.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

diff --git a/negotiator/default.c b/negotiator/default.c
index b8f45cf78..a9e52c943 100644
--- a/negotiator/default.c
+++ b/negotiator/default.c
@@ -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;
-- 
2.17.0.768.g1526ddbba1.dirty

Re: [PATCH v2 1/8] fetch-pack: split up everything_local()

[Brandon Williams]

On 06/06, Jonathan Tan wrote:
> 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().

Thanks, this is much cleaner.

> 
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 39 ++++++++++++++++++++++++++++++---------
>  1 file changed, 30 insertions(+), 9 deletions(-)
> 
> diff --git a/fetch-pack.c b/fetch-pack.c
> index a320ce987..5c87bb8bb 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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;
> -- 
> 2.17.0.768.g1526ddbba1.dirty
> 

-- 
Brandon Williams

Re: [PATCH v2 3/8] fetch-pack: directly end negotiation if ACK ready

[Brandon Williams]

On 06/06, Jonathan Tan wrote:
> 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.

> 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 <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/fetch-pack.c b/fetch-pack.c
> index 2812499a5..09f5c83c4 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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;
>  		}
> -- 
> 2.17.0.768.g1526ddbba1.dirty
> 

-- 
Brandon Williams

Re: [PATCH v2 4/8] fetch-pack: use ref adv. to prune "have" sent

[Brandon Williams]

On 06/06, Jonathan Tan wrote:
> 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.

Thanks for fixing this slight issue with v2.  Though maybe we need to
update the commit message here because a previous patch in this version
of the series broke up everything_local() into various parts so that it
is no longer responsible for enqueueing commits?

> 
> 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 <jonathantanmy@google.com>
> ---

-- 
Brandon Williams

Re: [PATCH v2 3/8] fetch-pack: directly end negotiation if ACK ready

[Brandon Williams]

On 06/14, Brandon Williams wrote:
> On 06/06, Jonathan Tan wrote:
> > 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.

Wait looks like a later commit does just this, maybe stick in a comment
saying a later patch is cleaning this up.

> 
> > 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 <jonathantanmy@google.com>
> > ---
> >  fetch-pack.c | 7 +++----
> >  1 file changed, 3 insertions(+), 4 deletions(-)
> > 
> > diff --git a/fetch-pack.c b/fetch-pack.c
> > index 2812499a5..09f5c83c4 100644
> > --- a/fetch-pack.c
> > +++ b/fetch-pack.c
> > @@ -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;
> >  		}
> > -- 
> > 2.17.0.768.g1526ddbba1.dirty
> > 
> 
> -- 
> Brandon Williams

-- 
Brandon Williams

Re: [PATCH v2 5/8] fetch-pack: make negotiation-related vars local

[Brandon Williams]

On 06/06, Jonathan Tan wrote:
> 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.

Ok I spoke too soon in my other mail.  You've cleaned this up by moving
these things to local stack vars but you still don't clear the priority
queue meaning that memory is now leaking.  I think you should insert a
call to clear the priority queue in the earlier patch before returning
from the fetch code.  This way you have a clear place to update that
call to clear in this patch so that you don't forget any memory leaks.

I know this may still change later on in this series but it should still
get taken care of to make the review process easier.

> 
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 104 +++++++++++++++++++++++++++++----------------------
>  1 file changed, 59 insertions(+), 45 deletions(-)
> 
> diff --git a/fetch-pack.c b/fetch-pack.c
> index 114207b8e..c31644bb9 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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;
> -- 
> 2.17.0.768.g1526ddbba1.dirty
> 

-- 
Brandon Williams

Re: [PATCH v2 8/8] negotiator/default: use better style in comments

[Brandon Williams]

On 06/06, Jonathan Tan wrote:
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
>  negotiator/default.c | 14 ++++++--------
>  1 file changed, 6 insertions(+), 8 deletions(-)
> 
> diff --git a/negotiator/default.c b/negotiator/default.c
> index b8f45cf78..a9e52c943 100644
> --- a/negotiator/default.c
> +++ b/negotiator/default.c
> @@ -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;
> -- 
> 2.17.0.768.g1526ddbba1.dirty
> 

Don't have this be a separate patch, squash it into the previous patch.

-- 
Brandon Williams

Re: [PATCH v2 5/8] fetch-pack: make negotiation-related vars local

[Junio C Hamano]

Jonathan Tan <jonathantanmy@google.com> writes:

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

Aside from Brandon's comments, I think passing these throughout the
callchain instead of having them as static-globals is a step in the
right direction.  Could you, however, give the structure a bit more
descriptive name, than simply "data"?  Anything the computer works
on is "data", and there must be something more specific than that
about this particular struct ;-)

Re: [PATCH v2 4/8] fetch-pack: use ref adv. to prune "have" sent

[Junio C Hamano]

Jonathan Tan <jonathantanmy@google.com> writes:

> +test_expect_success 'use ref advertisement to prune "have" lines sent' '
> +	rm -rf server client &&
> +	git init server &&
> +	test_commit -C server both_have_1 &&
> +	git -C server tag -d both_have_1 &&
> +	test_commit -C server both_have_2 &&
> +
> +	# In this test, the ref name that only the server has is a prefix of all
> +	# other refs. This is because in protocol v2, the client sends
> +	# "ref-prefix" to limit the ref advertisement. Naming the ref "bo" means
> +	# that "ref-prefix refs/tags/bo*" is sent, resulting in the client also
> +	# knowing about refs/tags/both_have_2, just as it would when it uses
> +	# protocol v0.

I have a mixed feeling about this test.

The client wants to fetch "bo" and nothing else in this example.
And refs "both_have_*", which have *nothing* to do with the ref the
client actually wants, is advertised merely because "both_have_*"
begins with "bo" with v2.  But that is an implementation detail that
we do not necessarily want to cast in stone, isn't it?  After all,
in future iterations of the protocol, we may find it too excessive
that we have to advertise both_have_1..both_have_10000 when the
client asks for bo and change either the pattern matching rule of
what "ref-prefix refs/tags/bo" matches, or the ref-prefix sent by
the client, and at that point, the expectation that both_have_2 is
sent as "have" but both_have_2^1 is not may have to change, no?

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

[PATCH v3 0/7] Refactor fetch negotiation into its own API

[Jonathan Tan]

Thanks, Brandon and Junio, for your comments.

Updates since v2:
 - nothing new in patches 1 and 2
 - patch 3: now clear priority queue unconditionally once we are done
   with it (as requested by Brandon in a comment for a later patch)
 - patch 4: updated commit message to not mention everything_local() (as
   pointed out by Brandon), updated test to not rely on the fact that
   fetch-pack uses prefix matching (thanks, Junio, for the observation)
 - patch 5: used a more descriptive name ("struct negotiation_state")
   for the struct, instead of "struct data"
 - squashed patch 8 into patch 7; this means that the comments are not
   moved verbatim, but for the reviewer, verbatim-ness of comments is
   probably not that important anyway

Jonathan Tan (7):
  fetch-pack: split up everything_local()
  fetch-pack: clear marks before re-marking
  fetch-pack: directly end negotiation if ACK ready
  fetch-pack: use ref adv. to prune "have" sent
  fetch-pack: make negotiation-related vars local
  fetch-pack: move common check and marking together
  fetch-pack: introduce negotiator API

 Makefile              |   2 +
 fetch-negotiator.c    |   8 ++
 fetch-negotiator.h    |  57 ++++++++++
 fetch-pack.c          | 255 ++++++++++++++----------------------------
 negotiator/default.c  | 176 +++++++++++++++++++++++++++++
 negotiator/default.h  |   8 ++
 object.h              |   3 +-
 t/t5500-fetch-pack.sh |  33 ++++++
 8 files changed, 373 insertions(+), 169 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

-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 1/7] fetch-pack: split up everything_local()

[Jonathan Tan]

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 <jonathantanmy@google.com>
---
 fetch-pack.c | 39 ++++++++++++++++++++++++++++++---------
 1 file changed, 30 insertions(+), 9 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index a320ce987..5c87bb8bb 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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;
-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 2/7] fetch-pack: clear marks before re-marking

[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 invocation of
mark_complete_and_common_ref() in do_fetch_pack() is useless.

(This cannot be reproduced with Git alone, because all transports that
come with Git support tag following.)

Therefore, move this clearing from find_common() to its
parent function do_fetch_pack(), right before it calls
mark_complete_and_common_ref().

This has been occurring since the commit that introduced the clearing of
marks, 420e9af498 ("Fix tag following", 2008-03-19).

The corresponding code for protocol v2 in do_fetch_pack_v2() does not
have this problem, as the clearing of flags is done before any marking
(whether by rev_list_insert_ref_oid() or
mark_complete_and_common_ref()).

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 fetch-pack.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 5c87bb8bb..2812499a5 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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);
@@ -1070,6 +1067,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 (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
 	mark_complete_and_common_ref(args, &ref);
 	filter_refs(args, &ref, sought, nr_sought);
 	if (everything_local(args, &ref)) {
-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 3/7] fetch-pack: directly end negotiation if ACK ready

[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 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 <jonathantanmy@google.com>
---
 fetch-pack.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 2812499a5..60adfc073 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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;
 }
-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 4/7] fetch-pack: use ref adv. to prune "have" sent

[Jonathan Tan]

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 mark_complete_and_common_ref(). 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,
mark_complete_and_common_ref() would not enqueue it.

If mark_complete_and_common_ref() were invoked first, as it is in
do_fetch_pack() for protocol v0, then mark_complete_and_common_ref()
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 <jonathantanmy@google.com>
---
 fetch-pack.c          |  6 +++---
 t/t5500-fetch-pack.sh | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 36 insertions(+), 3 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 60adfc073..806c40021 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -1392,9 +1392,6 @@ 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);
-			for_each_cached_alternate(insert_one_alternate_object);
-
 			/* Filter 'ref' by 'sought' and those that aren't local */
 			mark_complete_and_common_ref(args, &ref);
 			filter_refs(args, &ref, sought, nr_sought);
@@ -1402,6 +1399,9 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 				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);
 			break;
 		case FETCH_SEND_REQUEST:
 			if (send_fetch_request(fd[1], args, ref, &common,
diff --git a/t/t5500-fetch-pack.sh b/t/t5500-fetch-pack.sh
index d4f435155..e0cdc295d 100755
--- a/t/t5500-fetch-pack.sh
+++ b/t/t5500-fetch-pack.sh
@@ -755,6 +755,39 @@ test_expect_success 'fetching deepen' '
 	)
 '
 
+test_expect_success 'use ref advertisement to prune "have" lines sent' '
+	rm -rf server client &&
+	git init server &&
+	test_commit -C server both_have_1 &&
+	git -C server tag -d both_have_1 &&
+	test_commit -C server both_have_2 &&
+
+	git clone server client &&
+	test_commit -C server server_has &&
+	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 server_has both_have_2 &&
+	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 server_has both_have_2 &&
+	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 &&
-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 5/7] fetch-pack: make negotiation-related vars local

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

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.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 fetch-pack.c | 116 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 69 insertions(+), 47 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 806c40021..473e415c5 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -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 negotiation_state {
+	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,9 @@ 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 negotiation_state *ns,
+				      void (*cb)(struct negotiation_state *,
+					         struct object *))
 {
 	static int initialized;
 	static struct alternate_object_cache cache;
@@ -105,10 +111,11 @@ static void for_each_cached_alternate(void (*cb)(struct object *))
 	}
 
 	for (i = 0; i < cache.nr; i++)
-		cb(cache.items[i]);
+		cb(ns, cache.items[i]);
 }
 
-static void rev_list_push(struct commit *commit, int mark)
+static void rev_list_push(struct negotiation_state *ns,
+			  struct commit *commit, int mark)
 {
 	if (!(commit->object.flags & mark)) {
 		commit->object.flags |= mark;
@@ -116,19 +123,21 @@ static void rev_list_push(struct commit *commit, int mark)
 		if (parse_commit(commit))
 			return;
 
-		prio_queue_put(&rev_list, commit);
+		prio_queue_put(&ns->rev_list, commit);
 
 		if (!(commit->object.flags & COMMON))
-			non_common_revs++;
+			ns->non_common_revs++;
 	}
 }
 
-static int rev_list_insert_ref(const char *refname, const struct object_id *oid)
+static int rev_list_insert_ref(struct negotiation_state *ns,
+			       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(ns, (struct commit *)o, SEEN);
 
 	return 0;
 }
@@ -136,7 +145,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 +165,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 negotiation_state *ns, struct commit *commit,
 		int ancestors_only, int dont_parse)
 {
 	if (commit != NULL && !(commit->object.flags & COMMON)) {
@@ -166,12 +175,12 @@ static void mark_common(struct commit *commit,
 			o->flags |= COMMON;
 
 		if (!(o->flags & SEEN))
-			rev_list_push(commit, SEEN);
+			rev_list_push(ns, commit, SEEN);
 		else {
 			struct commit_list *parents;
 
 			if (!ancestors_only && !(o->flags & POPPED))
-				non_common_revs--;
+				ns->non_common_revs--;
 			if (!o->parsed && !dont_parse)
 				if (parse_commit(commit))
 					return;
@@ -179,7 +188,8 @@ static void mark_common(struct commit *commit,
 			for (parents = commit->parents;
 					parents;
 					parents = parents->next)
-				mark_common(parents->item, 0, dont_parse);
+				mark_common(ns, parents->item, 0,
+					    dont_parse);
 		}
 	}
 }
@@ -188,7 +198,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 negotiation_state *ns)
 {
 	struct commit *commit = NULL;
 
@@ -196,16 +206,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 (ns->rev_list.nr == 0 || ns->non_common_revs == 0)
 			return NULL;
 
-		commit = prio_queue_get(&rev_list);
+		commit = prio_queue_get(&ns->rev_list);
 		parse_commit(commit);
 		parents = commit->parents;
 
 		commit->object.flags |= POPPED;
 		if (!(commit->object.flags & COMMON))
-			non_common_revs--;
+			ns->non_common_revs--;
 
 		if (commit->object.flags & COMMON) {
 			/* do not send "have", and ignore ancestors */
@@ -220,9 +230,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(ns, parents->item, mark);
 			if (mark & COMMON)
-				mark_common(parents->item, 1, 0);
+				mark_common(ns, parents->item, 1, 0);
 			parents = parents->next;
 		}
 	}
@@ -296,9 +306,10 @@ 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 negotiation_state *ns,
+					struct object *obj)
 {
-	rev_list_insert_ref(NULL, &obj->oid);
+	rev_list_insert_ref(ns, NULL, &obj->oid);
 }
 
 #define INITIAL_FLUSH 16
@@ -321,7 +332,8 @@ 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 negotiation_state *ns,
+		       struct fetch_pack_args *args,
 		       int fd[2], struct object_id *result_oid,
 		       struct ref *refs)
 {
@@ -337,8 +349,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, ns);
+	for_each_cached_alternate(ns, insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
@@ -456,7 +468,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(ns))) {
 		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 +526,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(ns, commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
 					if (ack == ACK_ready)
@@ -704,7 +716,8 @@ 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 negotiation_state *unused,
+				    struct object *obj)
 {
 	mark_complete(&obj->oid);
 }
@@ -741,7 +754,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 negotiation_state *ns,
+					 struct fetch_pack_args *args,
 					 struct ref **refs)
 {
 	struct ref *ref;
@@ -792,7 +806,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 +824,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(ns, (struct commit *)o,
+					      COMMON_REF | SEEN);
 
-				mark_common((struct commit *)o, 1, 1);
+				mark_common(ns, (struct commit *)o, 1, 1);
 			}
 		}
 	}
@@ -995,6 +1010,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	struct object_id oid;
 	const char *agent_feature;
 	int agent_len;
+	struct negotiation_state ns = { { compare_commits_by_commit_date } };
 
 	sort_ref_list(&ref, ref_compare_name);
 	QSORT(sought, nr_sought, cmp_ref_by_name);
@@ -1070,13 +1086,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(&ns, 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(&ns, args, fd, &oid, ref) < 0)
 		if (!args->keep_pack)
 			/* When cloning, it is not unusual to have
 			 * no common commit.
@@ -1096,7 +1112,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);
+	clear_prio_queue(&ns.rev_list);
 	return ref;
 }
 
@@ -1158,13 +1174,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 negotiation_state *ns, 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(ns))) {
 		packet_buf_write(req_buf, "have %s\n", oid_to_hex(oid));
 		if (++haves_added >= *haves_to_send)
 			break;
@@ -1183,7 +1200,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 negotiation_state *ns, int fd_out,
+			      const struct fetch_pack_args *args,
 			      const struct ref *wants, struct oidset *common,
 			      int *haves_to_send, int *in_vain)
 {
@@ -1239,7 +1257,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(ns, &req_buf, haves_to_send, in_vain);
 	}
 
 	/* Send request */
@@ -1276,7 +1294,9 @@ 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 negotiation_state *ns,
+			struct packet_reader *reader,
+			struct oidset *common)
 {
 	/* received */
 	int received_ready = 0;
@@ -1295,7 +1315,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(ns, commit, 0, 1);
 			}
 			continue;
 		}
@@ -1373,6 +1393,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 negotiation_state ns = { { compare_commits_by_commit_date } };
 	packet_reader_init(&reader, fd[0], NULL, 0,
 			   PACKET_READ_CHOMP_NEWLINE);
 
@@ -1393,18 +1414,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(&ns, 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, &ns);
+			for_each_cached_alternate(&ns,
+						  insert_one_alternate_object);
 			break;
 		case FETCH_SEND_REQUEST:
-			if (send_fetch_request(fd[1], args, ref, &common,
+			if (send_fetch_request(&ns, fd[1], args, ref, &common,
 					       &haves_to_send, &in_vain))
 				state = FETCH_GET_PACK;
 			else
@@ -1412,7 +1434,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(&ns, &reader, &common)) {
 			case 2:
 				state = FETCH_GET_PACK;
 				break;
@@ -1441,7 +1463,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 		}
 	}
 
-	clear_prio_queue(&rev_list);
+	clear_prio_queue(&ns.rev_list);
 	oidset_clear(&common);
 	return ref;
 }
-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 6/7] fetch-pack: move common check and marking together

[Jonathan Tan]

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.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 fetch-pack.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 473e415c5..fb76d4017 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -505,11 +505,14 @@ static int find_common(struct negotiation_state *ns,
 				case ACK_continue: {
 					struct commit *commit =
 						lookup_commit(result_oid);
+					int was_common;
 					if (!commit)
 						die(_("invalid commit %s"), oid_to_hex(result_oid));
+					was_common = commit->object.flags & COMMON;
+					mark_common(ns, commit, 0, 1);
 					if (args->stateless_rpc
 					 && ack == ACK_common
-					 && !(commit->object.flags & COMMON)) {
+					 && !was_common) {
 						/* We need to replay the have for this object
 						 * on the next RPC request so the peer knows
 						 * it is in common with us.
@@ -526,7 +529,6 @@ static int find_common(struct negotiation_state *ns,
 					} else if (!args->stateless_rpc
 						   || ack != ACK_common)
 						in_vain = 0;
-					mark_common(ns, commit, 0, 1);
 					retval = 0;
 					got_continue = 1;
 					if (ack == ACK_ready)
-- 
2.17.0.582.gccdcbd54c4

[PATCH v3 7/7] fetch-pack: introduce negotiator API

[Jonathan Tan]

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 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 <jonathantanmy@google.com>
---
 Makefile             |   2 +
 fetch-negotiator.c   |   8 ++
 fetch-negotiator.h   |  57 ++++++++++++
 fetch-pack.c         | 205 ++++++++-----------------------------------
 negotiator/default.c | 176 +++++++++++++++++++++++++++++++++++++
 negotiator/default.h |   8 ++
 object.h             |   3 +-
 7 files changed, 292 insertions(+), 167 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

diff --git a/Makefile b/Makefile
index 1d27f3636..96f84d1dc 100644
--- a/Makefile
+++ b/Makefile
@@ -859,6 +859,7 @@ LIB_OBJS += ewah/ewah_bitmap.o
 LIB_OBJS += ewah/ewah_io.o
 LIB_OBJS += ewah/ewah_rlw.o
 LIB_OBJS += exec-cmd.o
+LIB_OBJS += fetch-negotiator.o
 LIB_OBJS += fetch-object.o
 LIB_OBJS += fetch-pack.o
 LIB_OBJS += fsck.o
@@ -891,6 +892,7 @@ LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
 LIB_OBJS += name-hash.o
+LIB_OBJS += negotiator/default.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
diff --git a/fetch-negotiator.c b/fetch-negotiator.c
new file mode 100644
index 000000000..2675d120f
--- /dev/null
+++ b/fetch-negotiator.c
@@ -0,0 +1,8 @@
+#include "git-compat-util.h"
+#include "fetch-negotiator.h"
+#include "negotiator/default.h"
+
+void fetch_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	default_negotiator_init(negotiator);
+}
diff --git a/fetch-negotiator.h b/fetch-negotiator.h
new file mode 100644
index 000000000..b1290aa9c
--- /dev/null
+++ b/fetch-negotiator.h
@@ -0,0 +1,57 @@
+#ifndef FETCH_NEGOTIATOR
+#define FETCH_NEGOTIATOR
+
+struct commit;
+
+/*
+ * An object that supplies the information needed to negotiate the contents of
+ * the to-be-sent packfile during a fetch.
+ *
+ * To set up the negotiator, call fetch_negotiator_init(), then known_common()
+ * (0 or more times), then add_tip() (0 or more times).
+ *
+ * Then, when "have" lines are required, call next(). Call ack() to report what
+ * the server tells us.
+ *
+ * Once negotiation is done, call release(). The negotiator then cannot be used
+ * (unless reinitialized with fetch_negotiator_init()).
+ */
+struct fetch_negotiator {
+	/*
+	 * Before negotiation starts, indicate that the server is known to have
+	 * this commit.
+	 */
+	void (*known_common)(struct fetch_negotiator *, struct commit *);
+
+	/*
+	 * Once this function is invoked, known_common() cannot be invoked any
+	 * more.
+	 *
+	 * Indicate that this commit and all its ancestors are to be checked
+	 * for commonality with the server.
+	 */
+	void (*add_tip)(struct fetch_negotiator *, struct commit *);
+
+	/*
+	 * Once this function is invoked, known_common() and add_tip() cannot
+	 * be invoked any more.
+	 *
+	 * Return the next commit that the client should send as a "have" line.
+	 */
+	const struct object_id *(*next)(struct fetch_negotiator *);
+
+	/*
+	 * Inform the negotiator that the server has the given commit. This
+	 * method must only be called on commits returned by next().
+	 */
+	int (*ack)(struct fetch_negotiator *, struct commit *);
+
+	void (*release)(struct fetch_negotiator *);
+
+	/* internal use */
+	void *data;
+};
+
+void fetch_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/fetch-pack.c b/fetch-pack.c
index fb76d4017..4b13d3389 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -15,10 +15,10 @@
 #include "connect.h"
 #include "transport.h"
 #include "version.h"
-#include "prio-queue.h"
 #include "sha1-array.h"
 #include "oidset.h"
 #include "packfile.h"
+#include "fetch-negotiator.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -36,13 +36,7 @@ static const char *alternate_shallow_file;
 
 /* Remember to update object flag allocation in object.h */
 #define COMPLETE	(1U << 0)
-#define COMMON		(1U << 1)
-#define COMMON_REF	(1U << 2)
-#define SEEN		(1U << 3)
-#define POPPED		(1U << 4)
-#define ALTERNATE	(1U << 5)
-
-static int marked;
+#define ALTERNATE	(1U << 1)
 
 /*
  * After sending this many "have"s if we do not get any new ACK , we
@@ -50,11 +44,6 @@ static int marked;
  */
 #define MAX_IN_VAIN 256
 
-struct negotiation_state {
-	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
@@ -97,8 +86,8 @@ static void cache_one_alternate(const char *refname,
 	cache->items[cache->nr++] = obj;
 }
 
-static void for_each_cached_alternate(struct negotiation_state *ns,
-				      void (*cb)(struct negotiation_state *,
+static void for_each_cached_alternate(struct fetch_negotiator *negotiator,
+				      void (*cb)(struct fetch_negotiator *,
 					         struct object *))
 {
 	static int initialized;
@@ -111,33 +100,17 @@ static void for_each_cached_alternate(struct negotiation_state *ns,
 	}
 
 	for (i = 0; i < cache.nr; i++)
-		cb(ns, cache.items[i]);
-}
-
-static void rev_list_push(struct negotiation_state *ns,
-			  struct commit *commit, int mark)
-{
-	if (!(commit->object.flags & mark)) {
-		commit->object.flags |= mark;
-
-		if (parse_commit(commit))
-			return;
-
-		prio_queue_put(&ns->rev_list, commit);
-
-		if (!(commit->object.flags & COMMON))
-			ns->non_common_revs++;
-	}
+		cb(negotiator, cache.items[i]);
 }
 
-static int rev_list_insert_ref(struct negotiation_state *ns,
+static int rev_list_insert_ref(struct fetch_negotiator *negotiator,
 			       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(ns, (struct commit *)o, SEEN);
+		negotiator->add_tip(negotiator, (struct commit *)o);
 
 	return 0;
 }
@@ -148,98 +121,6 @@ static int rev_list_insert_ref_oid(const char *refname, const struct object_id *
 	return rev_list_insert_ref(cb_data, refname, oid);
 }
 
-static int clear_marks(const char *refname, const struct object_id *oid,
-		       int flag, void *cb_data)
-{
-	struct object *o = deref_tag(parse_object(oid), refname, 0);
-
-	if (o && o->type == OBJ_COMMIT)
-		clear_commit_marks((struct commit *)o,
-				   COMMON | COMMON_REF | SEEN | POPPED);
-	return 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).
-*/
-
-static void mark_common(struct negotiation_state *ns, struct commit *commit,
-		int ancestors_only, int dont_parse)
-{
-	if (commit != NULL && !(commit->object.flags & COMMON)) {
-		struct object *o = (struct object *)commit;
-
-		if (!ancestors_only)
-			o->flags |= COMMON;
-
-		if (!(o->flags & SEEN))
-			rev_list_push(ns, commit, SEEN);
-		else {
-			struct commit_list *parents;
-
-			if (!ancestors_only && !(o->flags & POPPED))
-				ns->non_common_revs--;
-			if (!o->parsed && !dont_parse)
-				if (parse_commit(commit))
-					return;
-
-			for (parents = commit->parents;
-					parents;
-					parents = parents->next)
-				mark_common(ns, parents->item, 0,
-					    dont_parse);
-		}
-	}
-}
-
-/*
-  Get the next rev to send, ignoring the common.
-*/
-
-static const struct object_id *get_rev(struct negotiation_state *ns)
-{
-	struct commit *commit = NULL;
-
-	while (commit == NULL) {
-		unsigned int mark;
-		struct commit_list *parents;
-
-		if (ns->rev_list.nr == 0 || ns->non_common_revs == 0)
-			return NULL;
-
-		commit = prio_queue_get(&ns->rev_list);
-		parse_commit(commit);
-		parents = commit->parents;
-
-		commit->object.flags |= POPPED;
-		if (!(commit->object.flags & COMMON))
-			ns->non_common_revs--;
-
-		if (commit->object.flags & COMMON) {
-			/* do not send "have", and ignore ancestors */
-			commit = NULL;
-			mark = COMMON | SEEN;
-		} else if (commit->object.flags & COMMON_REF)
-			/* send "have", and ignore ancestors */
-			mark = COMMON | SEEN;
-		else
-			/* send "have", also for its ancestors */
-			mark = SEEN;
-
-		while (parents) {
-			if (!(parents->item->object.flags & SEEN))
-				rev_list_push(ns, parents->item, mark);
-			if (mark & COMMON)
-				mark_common(ns, parents->item, 1, 0);
-			parents = parents->next;
-		}
-	}
-
-	return &commit->object.oid;
-}
-
 enum ack_type {
 	NAK = 0,
 	ACK,
@@ -306,10 +187,10 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_object(struct negotiation_state *ns,
+static void insert_one_alternate_object(struct fetch_negotiator *negotiator,
 					struct object *obj)
 {
-	rev_list_insert_ref(ns, NULL, &obj->oid);
+	rev_list_insert_ref(negotiator, NULL, &obj->oid);
 }
 
 #define INITIAL_FLUSH 16
@@ -332,7 +213,7 @@ static int next_flush(int stateless_rpc, int count)
 	return count;
 }
 
-static int find_common(struct negotiation_state *ns,
+static int find_common(struct fetch_negotiator *negotiator,
 		       struct fetch_pack_args *args,
 		       int fd[2], struct object_id *result_oid,
 		       struct ref *refs)
@@ -349,8 +230,8 @@ static int find_common(struct negotiation_state *ns,
 	if (args->stateless_rpc && multi_ack == 1)
 		die(_("--stateless-rpc requires multi_ack_detailed"));
 
-	for_each_ref(rev_list_insert_ref_oid, ns);
-	for_each_cached_alternate(ns, insert_one_alternate_object);
+	for_each_ref(rev_list_insert_ref_oid, negotiator);
+	for_each_cached_alternate(negotiator, insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
@@ -468,7 +349,7 @@ static int find_common(struct negotiation_state *ns,
 	retval = -1;
 	if (args->no_dependents)
 		goto done;
-	while ((oid = get_rev(ns))) {
+	while ((oid = negotiator->next(negotiator))) {
 		packet_buf_write(&req_buf, "have %s\n", oid_to_hex(oid));
 		print_verbose(args, "have %s", oid_to_hex(oid));
 		in_vain++;
@@ -508,8 +389,7 @@ static int find_common(struct negotiation_state *ns,
 					int was_common;
 					if (!commit)
 						die(_("invalid commit %s"), oid_to_hex(result_oid));
-					was_common = commit->object.flags & COMMON;
-					mark_common(ns, commit, 0, 1);
+					was_common = negotiator->ack(negotiator, commit);
 					if (args->stateless_rpc
 					 && ack == ACK_common
 					 && !was_common) {
@@ -718,7 +598,7 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(struct negotiation_state *unused,
+static void mark_alternate_complete(struct fetch_negotiator *unused,
 				    struct object *obj)
 {
 	mark_complete(&obj->oid);
@@ -756,7 +636,7 @@ 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 negotiation_state *ns,
+static void mark_complete_and_common_ref(struct fetch_negotiator *negotiator,
 					 struct fetch_pack_args *args,
 					 struct ref **refs)
 {
@@ -825,12 +705,8 @@ static void mark_complete_and_common_ref(struct negotiation_state *ns,
 			if (!o || o->type != OBJ_COMMIT || !(o->flags & COMPLETE))
 				continue;
 
-			if (!(o->flags & SEEN)) {
-				rev_list_push(ns, (struct commit *)o,
-					      COMMON_REF | SEEN);
-
-				mark_common(ns, (struct commit *)o, 1, 1);
-			}
+			negotiator->known_common(negotiator,
+						 (struct commit *)o);
 		}
 	}
 
@@ -1012,7 +888,8 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 	struct object_id oid;
 	const char *agent_feature;
 	int agent_len;
-	struct negotiation_state ns = { { compare_commits_by_commit_date } };
+	struct fetch_negotiator negotiator;
+	fetch_negotiator_init(&negotiator);
 
 	sort_ref_list(&ref, ref_compare_name);
 	QSORT(sought, nr_sought, cmp_ref_by_name);
@@ -1085,16 +962,13 @@ 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;
-	mark_complete_and_common_ref(&ns, args, &ref);
+	mark_complete_and_common_ref(&negotiator, args, &ref);
 	filter_refs(args, &ref, sought, nr_sought);
 	if (everything_local(args, &ref)) {
 		packet_flush(fd[1]);
 		goto all_done;
 	}
-	if (find_common(&ns, args, fd, &oid, ref) < 0)
+	if (find_common(&negotiator, args, fd, &oid, ref) < 0)
 		if (!args->keep_pack)
 			/* When cloning, it is not unusual to have
 			 * no common commit.
@@ -1114,7 +988,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 		die(_("git fetch-pack: fetch failed."));
 
  all_done:
-	clear_prio_queue(&ns.rev_list);
+	negotiator.release(&negotiator);
 	return ref;
 }
 
@@ -1176,14 +1050,15 @@ static void add_common(struct strbuf *req_buf, struct oidset *common)
 	}
 }
 
-static int add_haves(struct negotiation_state *ns, struct strbuf *req_buf,
+static int add_haves(struct fetch_negotiator *negotiator,
+		     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(ns))) {
+	while ((oid = negotiator->next(negotiator))) {
 		packet_buf_write(req_buf, "have %s\n", oid_to_hex(oid));
 		if (++haves_added >= *haves_to_send)
 			break;
@@ -1202,7 +1077,7 @@ static int add_haves(struct negotiation_state *ns, struct strbuf *req_buf,
 	return ret;
 }
 
-static int send_fetch_request(struct negotiation_state *ns, int fd_out,
+static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,
 			      const struct fetch_pack_args *args,
 			      const struct ref *wants, struct oidset *common,
 			      int *haves_to_send, int *in_vain)
@@ -1259,7 +1134,7 @@ static int send_fetch_request(struct negotiation_state *ns, int fd_out,
 		add_common(&req_buf, common);
 
 		/* Add initial haves */
-		ret = add_haves(ns, &req_buf, haves_to_send, in_vain);
+		ret = add_haves(negotiator, &req_buf, haves_to_send, in_vain);
 	}
 
 	/* Send request */
@@ -1296,7 +1171,7 @@ static int process_section_header(struct packet_reader *reader,
 	return ret;
 }
 
-static int process_acks(struct negotiation_state *ns,
+static int process_acks(struct fetch_negotiator *negotiator,
 			struct packet_reader *reader,
 			struct oidset *common)
 {
@@ -1317,7 +1192,7 @@ static int process_acks(struct negotiation_state *ns,
 				struct commit *commit;
 				oidset_insert(common, &oid);
 				commit = lookup_commit(&oid);
-				mark_common(ns, commit, 0, 1);
+				negotiator->ack(negotiator, commit);
 			}
 			continue;
 		}
@@ -1395,7 +1270,8 @@ 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 negotiation_state ns = { { compare_commits_by_commit_date } };
+	struct fetch_negotiator negotiator;
+	fetch_negotiator_init(&negotiator);
 	packet_reader_init(&reader, fd[0], NULL, 0,
 			   PACKET_READ_CHOMP_NEWLINE);
 
@@ -1411,24 +1287,21 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			if (args->depth > 0 || args->deepen_since || args->deepen_not)
 				args->deepen = 1;
 
-			if (marked)
-				for_each_ref(clear_marks, NULL);
-			marked = 1;
-
 			/* Filter 'ref' by 'sought' and those that aren't local */
-			mark_complete_and_common_ref(&ns, args, &ref);
+			mark_complete_and_common_ref(&negotiator, 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, &ns);
-			for_each_cached_alternate(&ns,
+			for_each_ref(rev_list_insert_ref_oid, &negotiator);
+			for_each_cached_alternate(&negotiator,
 						  insert_one_alternate_object);
 			break;
 		case FETCH_SEND_REQUEST:
-			if (send_fetch_request(&ns, fd[1], args, ref, &common,
+			if (send_fetch_request(&negotiator, fd[1], args, ref,
+					       &common,
 					       &haves_to_send, &in_vain))
 				state = FETCH_GET_PACK;
 			else
@@ -1436,7 +1309,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 			break;
 		case FETCH_PROCESS_ACKS:
 			/* Process ACKs/NAKs */
-			switch (process_acks(&ns, &reader, &common)) {
+			switch (process_acks(&negotiator, &reader, &common)) {
 			case 2:
 				state = FETCH_GET_PACK;
 				break;
@@ -1465,7 +1338,7 @@ static struct ref *do_fetch_pack_v2(struct fetch_pack_args *args,
 		}
 	}
 
-	clear_prio_queue(&ns.rev_list);
+	negotiator.release(&negotiator);
 	oidset_clear(&common);
 	return ref;
 }
diff --git a/negotiator/default.c b/negotiator/default.c
new file mode 100644
index 000000000..382fc7772
--- /dev/null
+++ b/negotiator/default.c
@@ -0,0 +1,176 @@
+#include "cache.h"
+#include "default.h"
+#include "../commit.h"
+#include "../fetch-negotiator.h"
+#include "../prio-queue.h"
+#include "../refs.h"
+#include "../tag.h"
+
+/* Remember to update object flag allocation in object.h */
+#define COMMON		(1U << 2)
+#define COMMON_REF	(1U << 3)
+#define SEEN		(1U << 4)
+#define POPPED		(1U << 5)
+
+static int marked;
+
+struct negotiation_state {
+	struct prio_queue rev_list;
+	int non_common_revs;
+};
+
+static void rev_list_push(struct negotiation_state *ns,
+			  struct commit *commit, int mark)
+{
+	if (!(commit->object.flags & mark)) {
+		commit->object.flags |= mark;
+
+		if (parse_commit(commit))
+			return;
+
+		prio_queue_put(&ns->rev_list, commit);
+
+		if (!(commit->object.flags & COMMON))
+			ns->non_common_revs++;
+	}
+}
+
+static int clear_marks(const char *refname, const struct object_id *oid,
+		       int flag, void *cb_data)
+{
+	struct object *o = deref_tag(parse_object(oid), refname, 0);
+
+	if (o && o->type == OBJ_COMMIT)
+		clear_commit_marks((struct commit *)o,
+				   COMMON | COMMON_REF | SEEN | POPPED);
+	return 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).
+ */
+static void mark_common(struct negotiation_state *ns, struct commit *commit,
+		int ancestors_only, int dont_parse)
+{
+	if (commit != NULL && !(commit->object.flags & COMMON)) {
+		struct object *o = (struct object *)commit;
+
+		if (!ancestors_only)
+			o->flags |= COMMON;
+
+		if (!(o->flags & SEEN))
+			rev_list_push(ns, commit, SEEN);
+		else {
+			struct commit_list *parents;
+
+			if (!ancestors_only && !(o->flags & POPPED))
+				ns->non_common_revs--;
+			if (!o->parsed && !dont_parse)
+				if (parse_commit(commit))
+					return;
+
+			for (parents = commit->parents;
+					parents;
+					parents = parents->next)
+				mark_common(ns, parents->item, 0,
+					    dont_parse);
+		}
+	}
+}
+
+/*
+ * Get the next rev to send, ignoring the common.
+ */
+static const struct object_id *get_rev(struct negotiation_state *ns)
+{
+	struct commit *commit = NULL;
+
+	while (commit == NULL) {
+		unsigned int mark;
+		struct commit_list *parents;
+
+		if (ns->rev_list.nr == 0 || ns->non_common_revs == 0)
+			return NULL;
+
+		commit = prio_queue_get(&ns->rev_list);
+		parse_commit(commit);
+		parents = commit->parents;
+
+		commit->object.flags |= POPPED;
+		if (!(commit->object.flags & COMMON))
+			ns->non_common_revs--;
+
+		if (commit->object.flags & COMMON) {
+			/* do not send "have", and ignore ancestors */
+			commit = NULL;
+			mark = COMMON | SEEN;
+		} else if (commit->object.flags & COMMON_REF)
+			/* send "have", and ignore ancestors */
+			mark = COMMON | SEEN;
+		else
+			/* send "have", also for its ancestors */
+			mark = SEEN;
+
+		while (parents) {
+			if (!(parents->item->object.flags & SEEN))
+				rev_list_push(ns, parents->item, mark);
+			if (mark & COMMON)
+				mark_common(ns, parents->item, 1, 0);
+			parents = parents->next;
+		}
+	}
+
+	return &commit->object.oid;
+}
+
+static void known_common(struct fetch_negotiator *n, struct commit *c)
+{
+	if (!(c->object.flags & SEEN)) {
+		rev_list_push(n->data, c, COMMON_REF | SEEN);
+		mark_common(n->data, c, 1, 1);
+	}
+}
+
+static void add_tip(struct fetch_negotiator *n, struct commit *c)
+{
+	n->known_common = NULL;
+	rev_list_push(n->data, c, SEEN);
+}
+
+static const struct object_id *next(struct fetch_negotiator *n)
+{
+	n->known_common = NULL;
+	n->add_tip = NULL;
+	return get_rev(n->data);
+}
+
+static int ack(struct fetch_negotiator *n, struct commit *c)
+{
+	int known_to_be_common = !!(c->object.flags & COMMON);
+	mark_common(n->data, c, 0, 1);
+	return known_to_be_common;
+}
+
+static void release(struct fetch_negotiator *n)
+{
+	clear_prio_queue(&((struct negotiation_state *)n->data)->rev_list);
+	FREE_AND_NULL(n->data);
+}
+
+void default_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	struct negotiation_state *ns;
+	negotiator->known_common = known_common;
+	negotiator->add_tip = add_tip;
+	negotiator->next = next;
+	negotiator->ack = ack;
+	negotiator->release = release;
+	negotiator->data = ns = xcalloc(1, sizeof(*ns));
+	ns->rev_list.compare = compare_commits_by_commit_date;
+
+	if (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
+}
diff --git a/negotiator/default.h b/negotiator/default.h
new file mode 100644
index 000000000..d23a8f2fb
--- /dev/null
+++ b/negotiator/default.h
@@ -0,0 +1,8 @@
+#ifndef NEGOTIATOR_DEFAULT_H
+#define NEGOTIATOR_DEFAULT_H
+
+struct fetch_negotiator;
+
+void default_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/object.h b/object.h
index 5c1395500..7db4941d6 100644
--- a/object.h
+++ b/object.h
@@ -28,7 +28,8 @@ struct object_array {
 /*
  * object flag allocation:
  * revision.h:               0---------10                                26
- * fetch-pack.c:             0----5
+ * fetch-pack.c:             01
+ * negotiator/default.c:       2--5
  * walker.c:                 0-2
  * upload-pack.c:                4       11----------------19
  * builtin/blame.c:                        12-13
-- 
2.17.0.582.gccdcbd54c4

Re: [PATCH v3 3/7] fetch-pack: directly end negotiation if ACK ready

[Junio C Hamano]

Jonathan Tan <jonathantanmy@google.com> writes:

> 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 <jonathantanmy@google.com>
> ---
>  fetch-pack.c | 9 +++++----
>  1 file changed, 5 insertions(+), 4 deletions(-)

This makes more sense to me; I was wondering where the prio-queue
gets cleared, or leaking it is OK, while reading the previous round.

Thanks.

> diff --git a/fetch-pack.c b/fetch-pack.c
> index 2812499a5..60adfc073 100644
> --- a/fetch-pack.c
> +++ b/fetch-pack.c
> @@ -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;
>  }

Re: [PATCH v3 0/7] Refactor fetch negotiation into its own API

[Brandon Williams]

On 06/14, Jonathan Tan wrote:
> Thanks, Brandon and Junio, for your comments.
> 
> Updates since v2:
>  - nothing new in patches 1 and 2
>  - patch 3: now clear priority queue unconditionally once we are done
>    with it (as requested by Brandon in a comment for a later patch)
>  - patch 4: updated commit message to not mention everything_local() (as
>    pointed out by Brandon), updated test to not rely on the fact that
>    fetch-pack uses prefix matching (thanks, Junio, for the observation)
>  - patch 5: used a more descriptive name ("struct negotiation_state")
>    for the struct, instead of "struct data"
>  - squashed patch 8 into patch 7; this means that the comments are not
>    moved verbatim, but for the reviewer, verbatim-ness of comments is
>    probably not that important anyway

Thanks this series looks good now.

Reviewed-by: Brandon Williams <bmwill@google.com>

-- 
Brandon Williams