Re: [PATCH v5] fetch-pack: always allow fetching of literal SHA1s

Jonathan Nieder [off-list ref] writes:

quoted

+static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)
+{
+	for (; refs; refs = refs->next)
+		oidset_insert(oids, &refs->old_oid);
+}
+
+static int tip_oids_contain(struct oidset *tip_oids,
+			    struct ref *unmatched, struct ref *newlist,
+			    const struct object_id *id)
+{
+	if (!tip_oids->map.cmpfn) {

This feels like a layering violation.  Could it be e.g. a static inline
function oidset_is_initialized in oidset.h?

Surely it does.

Also, tip_oids_contain() uses unmatched and newlist only on the
first call, but the internal API this patch establishes gives an
illusion (confusion) that updating unmatched and newlist while
making repeated to calls to this function may affect the outcome of
tip_oids_contain() function.  In fact, doesn't the loop that calls
this function extend "newlist" by extending the list at its tail?

On Fri, May 12, 2017 at 1:14 AM, Jeff King [off-list ref] wrote:

7 more quoted lines

As far as I can tell, this seems to coincidentally work because SHA-1s
as strings compare less than any ref name (HEAD or refs/...) - if this
weren't the case, the "break" statement above might cause this line to
never be executed. I'm not sure if we want to rely on that.

13 more quoted lines

On Fri, May 12, 2017 at 03:01:35PM +0900, Junio C Hamano wrote:

Jonathan Nieder [off-list ref] writes:

quoted

quoted

+static void add_refs_to_oidset(struct oidset *oids, struct ref *refs)
+{
+	for (; refs; refs = refs->next)
+		oidset_insert(oids, &refs->old_oid);
+}
+
+static int tip_oids_contain(struct oidset *tip_oids,
+			    struct ref *unmatched, struct ref *newlist,
+			    const struct object_id *id)
+{
+	if (!tip_oids->map.cmpfn) {

This feels like a layering violation.  Could it be e.g. a static inline
function oidset_is_initialized in oidset.h?

Surely it does.

Also, tip_oids_contain() uses unmatched and newlist only on the
first call, but the internal API this patch establishes gives an
illusion (confusion) that updating unmatched and newlist while
making repeated to calls to this function may affect the outcome of
tip_oids_contain() function.  In fact, doesn't the loop that calls
this function extend "newlist" by extending the list at its tail?

It does, but only with elements whose oids were already in the set. So I
don't think it's wrong, but I agree the interface makes it a bit muddy.

The whole thing is much easier to follow if you just create the oidset
before chopping it up into two lists. But that loses the "lazy"
property, and you pay for the oidset even if there are no raw sha1s
requested. But it is nice and short. See the patch below (as a
replacement for what we've been discussing, not on top).

It's hard to resolve that because the loop that chops up the lists is
also the loop that is figuring out if there are leftover raw-sha1
names. But you could probably structure it like:

  1. Loop and see if we have unmatched names that look like sha1s.

  2. Set up the oidset from the two chopped-up lists if there are
     sha1 candidates (and if we aren't going to just send them
     regardless due to server options).

  3. Loop over the unmatched candidates and check them against the
     oidset.

That avoids the lazy-init, so pulling (2) out into a function results in
a better interface.

---

diff --git a/fetch-pack.c b/fetch-pack.c
index afb8b0502..4f3e8fa6b 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c

@@ -15,6 +15,7 @@
 #include "version.h"
 #include "prio-queue.h"
 #include "sha1-array.h"
+#include "oidset.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;

@@ -599,6 +600,9 @@ static void filter_refs(struct fetch_pack_args *args,
 	struct ref *newlist = NULL;
 	struct ref **newtail = &newlist;
 	struct ref *ref, *next;
+	struct oidset tip_oids = OIDSET_INIT;
+	int send_raw_oids = (allow_unadvertised_object_request &
+			     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
 	int i;
 
 	i = 0;

@@ -626,6 +630,9 @@ static void filter_refs(struct fetch_pack_args *args,
 		    (!args->deepen || !starts_with(ref->name, "refs/tags/")))
 			keep = 1;
 
+		if (!send_raw_oids)
+			oidset_insert(&tip_oids, &ref->old_oid);
+
 		if (keep) {
 			*newtail = ref;
 			ref->next = NULL;

@@ -647,8 +654,7 @@ static void filter_refs(struct fetch_pack_args *args,
 		    hashcmp(sha1, ref->old_oid.hash))
 			continue;
 
-		if ((allow_unadvertised_object_request &
-		    (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1))) {
+		if (send_raw_oids || oidset_contains(&tip_oids, &ref->old_oid)) {
 			ref->match_status = REF_MATCHED;
 			*newtail = copy_ref(ref);
 			newtail = &(*newtail)->next;

@@ -657,6 +663,8 @@ static void filter_refs(struct fetch_pack_args *args,
 		}
 	}
 	*refs = newlist;
+
+	oidset_clear(&tip_oids);
 }
 
 static void mark_alternate_complete(struct object *obj)

On Fri, May 12, 2017 at 12:59 AM, Jeff King [off-list ref] wrote:

On Fri, May 12, 2017 at 03:01:35PM +0900, Junio C Hamano wrote:

quoted

Also, tip_oids_contain() uses unmatched and newlist only on the
first call, but the internal API this patch establishes gives an
illusion (confusion) that updating unmatched and newlist while
making repeated to calls to this function may affect the outcome of
tip_oids_contain() function.  In fact, doesn't the loop that calls
this function extend "newlist" by extending the list at its tail?

It does, but only with elements whose oids were already in the set. So I
don't think it's wrong, but I agree the interface makes it a bit muddy.

To make the interface less muddy, would you agree with this (untested):

@@ -648,7 +669,9 @@ static void filter_refs(struct fetch_pack_args *args,
  continue;

  if ((allow_unadvertised_object_request &
-    (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1))) {
+     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1)) ||
+      (check_tip_oids_initialized(&tip_oids, unmatched, newlist) &&

oidset_contains(&tip_oids,
+     &ref->old_oid))) {
  ref->match_status = REF_MATCHED;
  *newtail = copy_ref(ref);
  newtail = &(*newtail)->next;

(making the function-to-abstract be merely an initialization one,
instead of one that does 2 things). That decreases the scope of the
function that Jonathan Nieder and Peff wanted, but it might be a
warranted reduction in scope.

On Fri, May 12, 2017 at 03:59:31AM -0400, Jeff King wrote:

It's hard to resolve that because the loop that chops up the lists is
also the loop that is figuring out if there are leftover raw-sha1
names. But you could probably structure it like:

  1. Loop and see if we have unmatched names that look like sha1s.

  2. Set up the oidset from the two chopped-up lists if there are
     sha1 candidates (and if we aren't going to just send them
     regardless due to server options).

  3. Loop over the unmatched candidates and check them against the
     oidset.

That avoids the lazy-init, so pulling (2) out into a function results in
a better interface.

Here that is for reference. It's a bit more complex than the other
solutions, requiring the unmatched list, the is_literal_sha1() helper,
and the oidset. But it avoids any extra allocation when it isn't
necessary, and drops the laziness.

I mostly did this to give the discussion something concrete to look at.
I'm actually OK with any of the options so far, as long as it does not
have any quadratic behavior. :)

diff --git a/fetch-pack.c b/fetch-pack.c
index afb8b0502..e167213c0 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c

@@ -15,6 +15,7 @@
 #include "version.h"
 #include "prio-queue.h"
 #include "sha1-array.h"
+#include "oidset.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;

@@ -592,13 +593,27 @@ static void mark_recent_complete_commits(struct fetch_pack_args *args,
 	}
 }
 
+static int is_literal_sha1(const struct ref *ref)
+{
+	struct object_id oid;
+	const char *end;
+	return !parse_oid_hex(ref->name, &oid, &end) &&
+	       !*end &&
+	       !oidcmp(&oid, &ref->old_oid);
+}
+
 static void filter_refs(struct fetch_pack_args *args,
 			struct ref **refs,
 			struct ref **sought, int nr_sought)
 {
 	struct ref *newlist = NULL;
 	struct ref **newtail = &newlist;
+	struct ref *unmatched = NULL;
 	struct ref *ref, *next;
+	struct oidset tip_oids = OIDSET_INIT;
+	int send_raw_oids = (allow_unadvertised_object_request &
+			     (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
+	int seeking_raw_oid = 0;
 	int i;
 
 	i = 0;

@@ -617,7 +632,8 @@ static void filter_refs(struct fetch_pack_args *args,
 				else if (cmp == 0) {
 					keep = 1; /* definitely have it */
 					sought[i]->match_status = REF_MATCHED;
-				}
+				} else if (is_literal_sha1(sought[i]))
+					seeking_raw_oid = 1;
 				i++;
 			}
 		}

@@ -631,24 +647,27 @@ static void filter_refs(struct fetch_pack_args *args,
 			ref->next = NULL;
 			newtail = &ref->next;
 		} else {
-			free(ref);
+			ref->next = unmatched;
+			unmatched = ref;
 		}
 	}
 
+	if (seeking_raw_oid && !send_raw_oids) {
+		for (ref = newlist; ref; ref = ref->next)
+			oidset_insert(&tip_oids, &ref->old_oid);
+		for (ref = unmatched; ref; ref = ref->next)
+			oidset_insert(&tip_oids, &ref->old_oid);
+	}
+
 	/* Append unmatched requests to the list */
 	for (i = 0; i < nr_sought; i++) {
-		unsigned char sha1[20];
-
 		ref = sought[i];
 		if (ref->match_status != REF_NOT_MATCHED)
 			continue;
-		if (get_sha1_hex(ref->name, sha1) ||
-		    ref->name[40] != '\0' ||
-		    hashcmp(sha1, ref->old_oid.hash))
+		if (!is_literal_sha1(ref))
 			continue;
 
-		if ((allow_unadvertised_object_request &
-		    (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1))) {
+		if (send_raw_oids || oidset_contains(&tip_oids, &ref->old_oid)) {
 			ref->match_status = REF_MATCHED;
 			*newtail = copy_ref(ref);
 			newtail = &(*newtail)->next;

@@ -656,6 +675,13 @@ static void filter_refs(struct fetch_pack_args *args,
 			ref->match_status = REF_UNADVERTISED_NOT_ALLOWED;
 		}
 	}
+
+	oidset_clear(&tip_oids);
+	for (ref = unmatched; ref; ref = next) {
+		next = ref->next;
+		free(ref);
+	}
+
 	*refs = newlist;
 }
 

Jonathan Tan wrote:

Yeah, that sounds nicer than anything I suggested.

nit that check_ would be clearer as ensure_

Thanks,
Jonathan

On Fri, May 12, 2017 at 11:00:36AM -0700, Jonathan Tan wrote:

quoted

@@ -617,7 +632,8 @@ static void filter_refs(struct fetch_pack_args *args,
                                else if (cmp == 0) {
                                        keep = 1; /* definitely have it */
                                        sought[i]->match_status = REF_MATCHED;
-                               }
+                               } else if (is_literal_sha1(sought[i]))
+                                       seeking_raw_oid = 1;

As far as I can tell, this seems to coincidentally work because SHA-1s
as strings compare less than any ref name (HEAD or refs/...) - if this
weren't the case, the "break" statement above might cause this line to
never be executed. I'm not sure if we want to rely on that.

Right, I was thinking we'd hit all of the sought refs in this loop, but
we don't necessarily (if we run out of remote refs to compare to).
Finishing it off with:

  /* scan the remainder of the requests */
  for (; i < nr_sought; i++)
	if (is_literal_sha1(...))

though it would probably be less confusing to just do a separate loop
after the original is done.

Anyway, it looks like your v6 just keeps the lazy approach, so this is
all moot.

-Peff