[RFC] helping smart-http/stateless-rpc fetch race

[RFC] helping smart-http/stateless-rpc fetch race

[Junio C Hamano]

A request to fetch from a client over smart HTTP protocol is served in
multiple steps. In the first round, the server side shows the set of refs
it has and their values, and the client picks from them and sends "I want
to fetch the history leading to these commits".

When the server tries to respond to this second request, its refs may have
progressed by a push from elsewhere. By design, we do not allow fetching
objects that are not at the tip of an advertised ref, and the server
rejects such a request. The client needs to try again, which is not ideal
especially for a busy server.

Teach --allow-non-tip option to upload-pack (which is the workhorse driven
by git-daemon and smart http server interface) that lets it server commits
that are not at the tip of any advertised ref, as long as they are
reachable from advertised refs.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * I'll leave it to interested parties who are more qualified than I am to
   update remote-curl nor http-backend to actually ask upload-pack to use
   this new logic ;-)

 upload-pack.c |  104 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 95 insertions(+), 9 deletions(-)

diff --git a/upload-pack.c b/upload-pack.c
index ce5cbbe..76be9ff 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -10,6 +10,7 @@
 #include "revision.h"
 #include "list-objects.h"
 #include "run-command.h"
+#include "sigchain.h"
 
 static const char upload_pack_usage[] = "git upload-pack [--strict] [--timeout=<n>] <dir>";
 
@@ -42,6 +43,7 @@ static int use_sideband;
 static int debug_fd;
 static int advertise_refs;
 static int stateless_rpc;
+static int allow_non_tip;
 
 static void reset_timeout(void)
 {
@@ -498,11 +500,87 @@ static int get_common_commits(void)
 	}
 }
 
+static void check_non_tip(void)
+{
+	static const char *argv[] = {
+		"rev-list", "--stdin", NULL,
+	};
+	static struct child_process cmd;
+	int i;
+	char namebuf[42]; /* ^ + SHA-1 + LF */
+
+	if (!allow_non_tip)
+		goto error;
+
+	cmd.argv = argv;
+	cmd.git_cmd = 1;
+	cmd.no_stderr = 1;
+	cmd.in = -1;
+	cmd.out = -1;
+
+	if (start_command(&cmd))
+		goto error;
+
+	/*
+	 * If rev-list --stdin encounters an unknown commit, it
+	 * terminates, which will cause SIGPIPE in the write loop
+	 * below.
+	 */
+	sigchain_push(SIGPIPE, SIG_IGN);
+
+	namebuf[0] = '^';
+	namebuf[41] = '\n';
+	for (i = get_max_object_index(); 0 < i; ) {
+		struct object *o = get_indexed_object(--i);
+		if (!(o->flags & OUR_REF))
+			continue;
+		memcpy(namebuf + 1, sha1_to_hex(o->sha1), 40);
+		if (write_in_full(cmd.in, namebuf, 42) < 0)
+			goto error;
+	}
+	namebuf[40] = '\n';
+	for (i = 0; i < want_obj.nr; i++) {
+		struct object *o = want_obj.objects[i].item;
+		if (o->flags & OUR_REF)
+			continue;
+		memcpy(namebuf, sha1_to_hex(o->sha1), 40);
+		if (write_in_full(cmd.in, namebuf, 41) < 0)
+			goto error;
+	}
+	close(cmd.in);
+
+	sigchain_pop(SIGPIPE);
+
+	/*
+	 * The commits out of the rev-list are not ancestors of
+	 * our ref.
+	 */
+	i = read_in_full(cmd.out, namebuf, 1);
+	if (i)
+		goto error;
+	close(cmd.out);
+
+	/*
+	 * rev-list may have died by encountering a bad commit
+	 * in the history, in which case we do want to bail out
+	 * even when it showed no commit.
+	 */
+	if (finish_command(&cmd))
+		goto error;
+
+	/* All the non-tip ones are ancestors of what we advertised */
+	return;
+
+error:
+	die("git upload-pack: not our ref");
+}
+
 static void receive_needs(void)
 {
 	struct object_array shallows = OBJECT_ARRAY_INIT;
 	static char line[1000];
 	int len, depth = 0;
+	int has_non_tip = 0;
 
 	shallow_nr = 0;
 	if (debug_fd)
@@ -559,26 +637,30 @@ static void receive_needs(void)
 		if (strstr(line+45, "include-tag"))
 			use_include_tag = 1;
 
-		/* We have sent all our refs already, and the other end
-		 * should have chosen out of them; otherwise they are
-		 * asking for nonsense.
-		 *
-		 * Hmph.  We may later want to allow "want" line that
-		 * asks for something like "master~10" (symbolic)...
-		 * would it make sense?  I don't know.
-		 */
 		o = lookup_object(sha1_buf);
-		if (!o || !(o->flags & OUR_REF))
+		if (!o)
 			die("git upload-pack: not our ref %s",
 			    sha1_to_hex(sha1_buf));
 		if (!(o->flags & WANTED)) {
 			o->flags |= WANTED;
+			if (!(o->flags & OUR_REF))
+				has_non_tip = 1;
 			add_object_array(o, NULL, &want_obj);
 		}
 	}
 	if (debug_fd)
 		write_str_in_full(debug_fd, "#E\n");
 
+	/*
+	 * We have sent all our refs already, and the other end
+	 * should have chosen out of them. When we are operating
+	 * in the stateless RPC mode, however, their choice may
+	 * have been based on the set of older refs advertised
+	 * by another process that handled the initial request.
+	 */
+	if (has_non_tip)
+		check_non_tip();
+
 	if (!use_sideband && daemon_mode)
 		no_progress = 1;
 
@@ -720,6 +802,10 @@ int main(int argc, char **argv)
 			stateless_rpc = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--allow-non-tip")) {
+			allow_non_tip = 1;
+			continue;
+		}
 		if (!strcmp(arg, "--strict")) {
 			strict = 1;
 			continue;

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Shawn Pearce]

On Fri, Aug 5, 2011 at 13:54, Junio C Hamano <gitster@pobox.com> wrote:
> A request to fetch from a client over smart HTTP protocol is served in
> multiple steps. In the first round, the server side shows the set of refs
> it has and their values, and the client picks from them and sends "I want
> to fetch the history leading to these commits".
>
> When the server tries to respond to this second request, its refs may have
> progressed by a push from elsewhere. By design, we do not allow fetching
> objects that are not at the tip of an advertised ref, and the server
> rejects such a request. The client needs to try again, which is not ideal
> especially for a busy server.
>
> Teach --allow-non-tip option to upload-pack (which is the workhorse driven
> by git-daemon and smart http server interface) that lets it server commits
> that are not at the tip of any advertised ref, as long as they are
> reachable from advertised refs.
>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
>
>  * I'll leave it to interested parties who are more qualified than I am to
>   update remote-curl nor http-backend to actually ask upload-pack to use
>   this new logic ;-)

Why a new --allow-non-tip flag? Why not always do this with the
existing --stateless-rpc flag? I think the only time it is reasonable
to allow a non-tip want line is during the smart HTTP usage where the
request has spanned processes and the references may have moved in the
interm. Over a git:// or SSH where its the same server process and the
refs were cached at startup (and thus cannot move), it isn't
reasonable to allow a non-tip want.

Otherwise the patch looks good to me. This should fix some issues with
very busy repositories being fetched over smart HTTP.

-- 
Shawn.

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Junio C Hamano]

Shawn Pearce <spearce@spearce.org> writes:

> Why a new --allow-non-tip flag? Why not always do this with the
> existing --stateless-rpc flag?

It certainly would be much easier from implementation point of view, but I
did it that way for two and half reasons:

 (1) It might make sense to give admins who run upload-pack not behind
     smart-http an option to allow fetching from a non-tip; and

 (2) It also might make sense to let admins who do run upload-pack behind
     smart-http force re-fetching when the race is encountered.

and the remaining half-reason was that I was too lazy to think things
through to refute the above two "might make sense" and convince myself
that they should instead be "is not necessary".

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Shawn Pearce <spearce@spearce.org> writes:
>
>> Why a new --allow-non-tip flag? Why not always do this with the
>> existing --stateless-rpc flag?
>
> It certainly would be much easier from implementation point of view, but I
> did it that way for two and half reasons:
>
>  (1) It might make sense to give admins who run upload-pack not behind
>      smart-http an option to allow fetching from a non-tip; and
>
>  (2) It also might make sense to let admins who do run upload-pack behind
>      smart-http force re-fetching when the race is encountered.
>
> and the remaining half-reason was that I was too lazy to think things
> through to refute the above two "might make sense" and convince myself
> that they should instead be "is not necessary".

I still haven't convinced myself but here is a simplified one without the
new option (hence no need to touch the smart-http infrastructure).

-- >8 --
Subject: [PATCH] helping smart-http/stateless-rpc fetch race

A request to fetch from a client over smart HTTP protocol is served in
multiple steps. In the first round, the server side shows the set of refs
it has and their values, and the client picks from them and sends "I want
to fetch the history leading to these commits".

When the server tries to respond to this second request, its refs may have
progressed by a push from elsewhere. By design, we do not allow fetching
objects that are not at the tip of an advertised ref, and the server
rejects such a request. The client needs to try again, which is not ideal
especially for a busy server.

Teach upload-pack (which is the workhorse driven by git-daemon and smart
http server interface) that it is OK for a smart-http client to ask for
commits that are not at the tip of any advertised ref, as long as they are
reachable from advertised refs.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 upload-pack.c |  108 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 99 insertions(+), 9 deletions(-)

diff --git a/upload-pack.c b/upload-pack.c
index ce5cbbe..30cf941 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -10,6 +10,7 @@
 #include "revision.h"
 #include "list-objects.h"
 #include "run-command.h"
+#include "sigchain.h"
 
 static const char upload_pack_usage[] = "git upload-pack [--strict] [--timeout=<n>] <dir>";
 
@@ -498,11 +499,96 @@ static int get_common_commits(void)
 	}
 }
 
+static void check_non_tip(void)
+{
+	static const char *argv[] = {
+		"rev-list", "--stdin", NULL,
+	};
+	static struct child_process cmd;
+	struct object *o;
+	char namebuf[42]; /* ^ + SHA-1 + LF */
+	int i;
+
+	/* In the normal in-process case non-tip request can never happen */
+	if (!stateless_rpc)
+		goto error;
+
+	cmd.argv = argv;
+	cmd.git_cmd = 1;
+	cmd.no_stderr = 1;
+	cmd.in = -1;
+	cmd.out = -1;
+
+	if (start_command(&cmd))
+		goto error;
+
+	/*
+	 * If rev-list --stdin encounters an unknown commit, it
+	 * terminates, which will cause SIGPIPE in the write loop
+	 * below.
+	 */
+	sigchain_push(SIGPIPE, SIG_IGN);
+
+	namebuf[0] = '^';
+	namebuf[41] = '\n';
+	for (i = get_max_object_index(); 0 < i; ) {
+		o = get_indexed_object(--i);
+		if (!(o->flags & OUR_REF))
+			continue;
+		memcpy(namebuf + 1, sha1_to_hex(o->sha1), 40);
+		if (write_in_full(cmd.in, namebuf, 42) < 0)
+			goto error;
+	}
+	namebuf[40] = '\n';
+	for (i = 0; i < want_obj.nr; i++) {
+		o = want_obj.objects[i].item;
+		if (o->flags & OUR_REF)
+			continue;
+		memcpy(namebuf, sha1_to_hex(o->sha1), 40);
+		if (write_in_full(cmd.in, namebuf, 41) < 0)
+			goto error;
+	}
+	close(cmd.in);
+
+	sigchain_pop(SIGPIPE);
+
+	/*
+	 * The commits out of the rev-list are not ancestors of
+	 * our ref.
+	 */
+	i = read_in_full(cmd.out, namebuf, 1);
+	if (i)
+		goto error;
+	close(cmd.out);
+
+	/*
+	 * rev-list may have died by encountering a bad commit
+	 * in the history, in which case we do want to bail out
+	 * even when it showed no commit.
+	 */
+	if (finish_command(&cmd))
+		goto error;
+
+	/* All the non-tip ones are ancestors of what we advertised */
+	return;
+
+error:
+	/* Pick one of them (we know there at least is one) */
+	for (i = 0; i < want_obj.nr; i++) {
+		o = want_obj.objects[i].item;
+		if (!(o->flags & OUR_REF))
+			break;
+	}
+	die("git upload-pack: not our ref %s",
+	    sha1_to_hex(o->sha1));
+}
+
 static void receive_needs(void)
 {
 	struct object_array shallows = OBJECT_ARRAY_INIT;
 	static char line[1000];
 	int len, depth = 0;
+	int has_non_tip = 0;
 
 	shallow_nr = 0;
 	if (debug_fd)
@@ -559,26 +645,30 @@ static void receive_needs(void)
 		if (strstr(line+45, "include-tag"))
 			use_include_tag = 1;
 
-		/* We have sent all our refs already, and the other end
-		 * should have chosen out of them; otherwise they are
-		 * asking for nonsense.
-		 *
-		 * Hmph.  We may later want to allow "want" line that
-		 * asks for something like "master~10" (symbolic)...
-		 * would it make sense?  I don't know.
-		 */
 		o = lookup_object(sha1_buf);
-		if (!o || !(o->flags & OUR_REF))
+		if (!o)
 			die("git upload-pack: not our ref %s",
 			    sha1_to_hex(sha1_buf));
 		if (!(o->flags & WANTED)) {
 			o->flags |= WANTED;
+			if (!(o->flags & OUR_REF))
+				has_non_tip = 1;
 			add_object_array(o, NULL, &want_obj);
 		}
 	}
 	if (debug_fd)
 		write_str_in_full(debug_fd, "#E\n");
 
+	/*
+	 * We have sent all our refs already, and the other end
+	 * should have chosen out of them. When we are operating
+	 * in the stateless RPC mode, however, their choice may
+	 * have been based on the set of older refs advertised
+	 * by another process that handled the initial request.
+	 */
+	if (has_non_tip)
+		check_non_tip();
+
 	if (!use_sideband && daemon_mode)
 		no_progress = 1;
 
-- 
1.7.6.409.ge7a85

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Sverre Rabbelier]

Heya,

On Mon, Aug 8, 2011 at 19:13, Junio C Hamano <gitster@pobox.com> wrote:
>>  (1) It might make sense to give admins who run upload-pack not behind
>>      smart-http an option to allow fetching from a non-tip; and

You said earlier it isn't needed since the server process caches the
refs for git and ssh, that leaves dumb-http right? If that is indeed
the case I think we can just argue that since smart-http is our
solution to the http problems, if admins want to make life easier for
http fetches on busy repositories they should be using smart-http.

>>  (2) It also might make sense to let admins who do run upload-pack behind
>>      smart-http force re-fetching when the race is encountered.

This would mean that if you're running smart-http without this option
enabled (because, say, you don't know it exists), your users have to
re-fetch (a lot). The only upside would be that if the server _knows_
what the user is asking for is outdated, that the user will know this
right away. That doesn't fly though, since we allow exactly that for
git and ssh transfer.

-- 
Cheers,

Sverre Rabbelier

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Ilari Liusvaara]

On Mon, Aug 08, 2011 at 11:05:27PM +0200, Sverre Rabbelier wrote:
> Heya,
> 
> On Mon, Aug 8, 2011 at 19:13, Junio C Hamano <gitster@pobox.com> wrote:
> >>  (1) It might make sense to give admins who run upload-pack not behind
> >>      smart-http an option to allow fetching from a non-tip; and
> 
> You said earlier it isn't needed since the server process caches the
> refs for git and ssh, that leaves dumb-http right?

It seems that everything currently possible falls into three
categories:

1) Stateful upload-pack (git://, file://, ssh://, CONNECT): No fix
needed.
2) Stateless upload-pack (smart http://, some bizarre helper):
Needs fix to avoid races.
3) Dumb protocols (dumb http://, ftp://, rsync://): Won't invoke
upload-pack anyway, no fix needed.

So I think that the only thing that needs the option to allow
fetching from non-tips is anything using --stateless-rpc.

-Ilari

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Junio C Hamano]

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> writes:

> On Mon, Aug 08, 2011 at 11:05:27PM +0200, Sverre Rabbelier wrote:
>> Heya,
>> 
>> On Mon, Aug 8, 2011 at 19:13, Junio C Hamano <gitster@pobox.com> wrote:
>> >>  (1) It might make sense to give admins who run upload-pack not behind
>> >>      smart-http an option to allow fetching from a non-tip; and
>> 
>> You said earlier it isn't needed since the server process caches the
>> refs for git and ssh, that leaves dumb-http right?
>
> It seems that everything currently possible falls into three
> categories:
>
> 1) Stateful upload-pack (git://, file://, ssh://, CONNECT): No fix
> needed.
> 2) Stateless upload-pack (smart http://, some bizarre helper):
> Needs fix to avoid races.
> 3) Dumb protocols (dumb http://, ftp://, rsync://): Won't invoke
> upload-pack anyway, no fix needed.
>
> So I think that the only thing that needs the option to allow
> fetching from non-tips is anything using --stateless-rpc.

These (1) and (2) were never meant to be fixes to work around the
smart-http protocol limitation; I know "No fix _needed_" and it was never
a consideration to decide (or choose not to decide) about these two
points.

A separate option would allow admins to let their clients ask to fetch
4bc5fbf (that is v0.99~2) even if that commit is not at the tip of any ref
if they choose to. That is what (1) is about, and people who do not want
a separate option needs to argue that it is an unnecessary "feature".

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> A separate option would allow admins to let their clients ask to fetch
> 4bc5fbf (that is v0.99~2) even if that commit is not at the tip of any ref
> if they choose to. That is what (1) is about, and people who do not want
> a separate option needs to argue that it is an unnecessary "feature".

By the way, I personally do not think it is necessary, but as long timers
on the list may recall, this has come up on the list for a few times.

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Shawn Pearce]

On Mon, Aug 8, 2011 at 16:26, Junio C Hamano <gitster@pobox.com> wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>> A separate option would allow admins to let their clients ask to fetch
>> 4bc5fbf (that is v0.99~2) even if that commit is not at the tip of any ref
>> if they choose to. That is what (1) is about, and people who do not want
>> a separate option needs to argue that it is an unnecessary "feature".
>
> By the way, I personally do not think it is necessary, but as long timers
> on the list may recall, this has come up on the list for a few times.

My feeling is clients aren't likely to do this, or grow this feature
anytime soon, so why add a backend option for it now? Lets add the
feature when the feature is necessary... and right now just fix the
race in smart HTTP.

-- 
Shawn.

Re: [RFC] helping smart-http/stateless-rpc fetch race

[Junio C Hamano]

Shawn Pearce <spearce@spearce.org> writes:

> On Mon, Aug 8, 2011 at 16:26, Junio C Hamano <gitster@pobox.com> wrote:
>> Junio C Hamano <gitster@pobox.com> writes:
>>
>>> A separate option would allow admins to let their clients ask to fetch
>>> 4bc5fbf (that is v0.99~2) even if that commit is not at the tip of any ref
>>> if they choose to. That is what (1) is about, and people who do not want
>>> a separate option needs to argue that it is an unnecessary "feature".
>>
>> By the way, I personally do not think it is necessary, but as long timers
>> on the list may recall, this has come up on the list for a few times.
>
> My feeling is clients aren't likely to do this, or grow this feature
> anytime soon, so why add a backend option for it now? Lets add the
> feature when the feature is necessary... and right now just fix the
> race in smart HTTP.

Yes, that is what is queued in today's 'pu'.