{"thread":{"id":"2174","subject":"[PATCH] Do not call git-rev-list from git-fetch-pack","startedAt":"2005-10-21T02:15:52Z","lastAt":"2005-10-22T00:35:42Z","messageCount":9,"participants":["Johannes Schindelin","Junio C Hamano","Daniel Barkalow"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"10398","messageId":"Pine.LNX.4.63.0510210413210.26388@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"2174","inReplyTo":null,"subject":"[PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-10-21T02:15:52Z","receivedAt":"2005-10-21T02:15:52Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"It is much easier to avoid sending unneeded data when putting the rev list\ntogether in a customized manner. In particular, the tips of the local\nbranches are sent first, and only then their ancestors.\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n\n---\n\n\tThis supersedes my earlier attempt. SHA1s of tags are no longer\n\tsent via \"have\" lines. This makes the code much simpler. Also,\n\tit does not buy us much to send them:\n\n\tEither we have the tag object already, pointed to by a ref (thus \n\tnot \"want\"ing it in the first place), or we fetch at most\n\ta couple of tag objects we already have.\n\n fetch-pack.c |  139 ++++++++++++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 106 insertions(+), 33 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 8566ab1..260de90 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -13,18 +13,102 @@ static const char fetch_pack_usage[] =\n static const char *exec = \"git-upload-pack\";\n \n #define COMPLETE\t(1U << 0)\n+#define COMMON\t\t(1U << 1)\n+#define COMMON_REF\t(1U << 2)\n+#define SEEN\t\t(1U << 3)\n+\n+struct commit_list *rev_list = NULL;\n+\n+static int rev_list_insert(const char *path, const unsigned char *sha1)\n+{\n+\tstruct object *o = deref_tag(parse_object(sha1));\n+\n+\t/*\n+\t   The real problem is that find_common will stop very soon\n+\t   after seeing a common revision.\n+\n+\t   However, that does not always make sense. Example:\n+\n+\t   Branch1 has 40 commits since it last merged with branch2,\n+\t   and branch2 has 2 more commits since then.\n+\n+\t   On the other end, branch1 is up-to-date, but branch2 is not.\n+\t   When fetching branch1, the 40 commits get sent, the first\n+\t   is acknowledged as common, and the local head of branch2\n+\t   never gets sent.\n+\n+\t   As a consequence, the whole history of branch2\n+\t   (git-rev-list branch2 ^branch1) gets packed and transmitted.\n+\n+\t   The workaround is to pretend that the tips of the local\n+\t   branches are 10 years younger, so that they are sent before\n+\t   everything else.\n+\t*/\n+\n+\tif (o->type == commit_type && !(o->flags & SEEN)) {\n+\t\tstruct commit *commit = (struct commit *)o;\n+\t\to->flags |= SEEN;\n+\t\t/* The head's tips get handled before everything else. */\n+\t\tcommit->date += 10*365*86400;\n+\t\tinsert_by_date(commit, &rev_list);\n+\t}\n+\n+\treturn 0;\n+}\n+\n+/*\n+  Get the next rev to send, ignoring the common.\n+*/\n+\n+static const unsigned char* get_rev()\n+{\n+\tstruct commit *commit = NULL;\n+\n+\twhile (commit == NULL) {\n+\t\tunsigned int mark;\n+\n+\t\tif (rev_list == NULL)\n+\t\t\treturn NULL;\n+\n+\t\tcommit = rev_list->item;\n+\n+\t\tif (commit->object.flags & COMMON) {\n+\t\t\t/* do not send \"have\", and ignore ancestors */\n+\t\t\tcommit = NULL;\n+\t\t\tmark = COMMON | SEEN;\n+\t\t} else if (commit->object.flags & COMMON_REF)\n+\t\t\t/* send \"have\", and ignore ancestors */\n+\t\t\tmark = COMMON | SEEN;\n+\t\telse\n+\t\t\t/* send \"have\", also for its ancestors */\n+\t\t\tmark = SEEN;\n+\n+\t\tpop_most_recent_commit(&rev_list, mark);\n+\t}\n+\n+\treturn commit->object.sha1;\n+}\n+\n+static void mark_common(const unsigned char* sha1)\n+{\n+\tstruct object *o = lookup_object(sha1);\n+\n+\tif (o != NULL && !(o->flags & COMMON)) {\n+\t\to->flags |= COMMON;\n+\t\tif (o->type == commit_type)\n+\t\t\tinsert_by_date((struct commit *)o, &rev_list);\n+\t}\n+}\n \n static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t       struct ref *refs)\n {\n \tint fetching;\n-\tstatic char line[1000];\n-\tstatic char rev_command[1024];\n-\tint count = 0, flushes = 0, retval, rev_command_len;\n-\tFILE *revs;\n+\tint count = 0, flushes = 0, retval;\n+\tconst unsigned char *sha1;\n+\n+\tfor_each_ref(rev_list_insert);\n \n-\tstrcpy(rev_command, \"git-rev-list $(git-rev-parse --all)\");\n-\trev_command_len = strlen(rev_command);\n \tfetching = 0;\n \tfor ( ; refs ; refs = refs->next) {\n \t\tunsigned char *remote = refs->old_sha1;\n@@ -42,25 +126,17 @@ static int find_common(int fd[2], unsign\n \t\t */\n \t\tif (((o = lookup_object(remote)) != NULL) &&\n \t\t    (o->flags & COMPLETE)) {\n-\t\t\tstruct commit_list *p;\n-\t\t\tstruct commit *commit =\n-\t\t\t\t(struct commit *) (o = deref_tag(o));\n-\t\t\tif (!o)\n-\t\t\t\tgoto repair;\n-\t\t\tif (o->type != commit_type)\n-\t\t\t\tcontinue;\n-\t\t\tp = commit->parents;\n-\t\t\twhile (p &&\n-\t\t\t       rev_command_len + 44 < sizeof(rev_command)) {\n-\t\t\t\tsnprintf(rev_command + rev_command_len, 44,\n-\t\t\t\t\t \" ^%s\",\n-\t\t\t\t\t sha1_to_hex(p->item->object.sha1));\n-\t\t\t\trev_command_len += 43;\n-\t\t\t\tp = p->next;\n+\t\t\to = deref_tag(o);\n+\t\t\to->flags |= COMMON_REF;\n+\n+\t\t\tif (o->type == commit_type && !(o->flags & SEEN)) {\n+\t\t\t\to->flags |= SEEN;\n+\t\t\t\tinsert_by_date((struct commit *)o, &rev_list);\n \t\t\t}\n+\n \t\t\tcontinue;\n \t\t}\n-\trepair:\n+\n \t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n \t\tfetching++;\n \t}\n@@ -68,21 +144,16 @@ static int find_common(int fd[2], unsign\n \tif (!fetching)\n \t\treturn 1;\n \n-\trevs = popen(rev_command, \"r\");\n-\tif (!revs)\n-\t\tdie(\"unable to run 'git-rev-list'\");\n-\n \tflushes = 1;\n \tretval = -1;\n-\twhile (fgets(line, sizeof(line), revs) != NULL) {\n-\t\tunsigned char sha1[20];\n-\t\tif (get_sha1_hex(line, sha1))\n-\t\t\tdie(\"git-fetch-pack: expected object name, got crud\");\n+\twhile ((sha1 = get_rev())) {\n \t\tpacket_write(fd[1], \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (verbose)\n \t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (!(31 & ++count)) {\n \t\t\tpacket_flush(fd[1]);\n+\t\t\tif (verbose)\n+\t\t\t\tfprintf(stderr, \"flush\\n\");\n \t\t\tflushes++;\n \n \t\t\t/*\n@@ -92,16 +163,17 @@ static int find_common(int fd[2], unsign\n \t\t\tif (count == 32)\n \t\t\t\tcontinue;\n \t\t\tif (get_ack(fd[0], result_sha1)) {\n+\t\t\t\tmark_common(result_sha1);\n \t\t\t\tflushes = 0;\n \t\t\t\tretval = 0;\n \t\t\t\tif (verbose)\n-\t\t\t\t\tfprintf(stderr, \"got ack\\n\");\n+\t\t\t\t\tfprintf(stderr, \"got ack %s\\n\",\n+\t\t\t\t\t\tsha1_to_hex(result_sha1));\n \t\t\t\tbreak;\n \t\t\t}\n \t\t\tflushes--;\n \t\t}\n \t}\n-\tpclose(revs);\n \tpacket_write(fd[1], \"done\\n\");\n \tif (verbose)\n \t\tfprintf(stderr, \"done\\n\");\n@@ -109,7 +181,8 @@ static int find_common(int fd[2], unsign\n \t\tflushes--;\n \t\tif (get_ack(fd[0], result_sha1)) {\n \t\t\tif (verbose)\n-\t\t\t\tfprintf(stderr, \"got ack\\n\");\n+\t\t\t\tfprintf(stderr, \"got ack %s\\n\",\n+\t\t\t\t\tsha1_to_hex(result_sha1));\n \t\t\treturn 0;\n \t\t}\n \t}\n"},{"id":"10419","messageId":"7virvrw8w1.fsf@assigned-by-dhcp.cox.net","threadId":"2174","inReplyTo":"Pine.LNX.4.63.0510210413210.26388@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-21T08:51:10Z","receivedAt":"2005-10-21T08:51:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> +\t   Branch1 has 40 commits since it last merged with branch2,\n> +\t   and branch2 has 2 more commits since then.\n> +\n> +\t   On the other end, branch1 is up-to-date, but branch2 is not.\n> +\t   When fetching branch1, the 40 commits get sent, the first\n> +\t   is acknowledged as common, and the local head of branch2\n> +\t   never gets sent.\n> +\n> +\t   As a consequence, the whole history of branch2\n> +\t   (git-rev-list branch2 ^branch1) gets packed and transmitted.\n\nArrrgggggggh.  The description above captures the essense of the\nproblem very well, but faking dates and still popping by recency\nlooks like a really ugly hack to me.\n\nWouldn't it be cleaner if you traversed commits starting from\nlocal refs, and assign distance from the tip of the branch to\neach object (use generic object->util field for it), and\nmaintain an object_list that is sorted by depth, similar to\ncommit_list sorted by commit date?  Then you can pop from the\nlist by depth, closer to tip first, and tell the other end that\nyou have branch1, branch2, branch1^, branch2^, branch1~2,\nbranch2~1,...  which is the order the above situation benefits\nfrom.\n"},{"id":"10421","messageId":"Pine.LNX.4.63.0510211111440.4950@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"2174","inReplyTo":"7virvrw8w1.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-10-21T09:35:21Z","receivedAt":"2005-10-21T09:35:21Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 21 Oct 2005, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > +\t   Branch1 has 40 commits since it last merged with branch2,\n> > +\t   and branch2 has 2 more commits since then.\n> > +\n> > +\t   On the other end, branch1 is up-to-date, but branch2 is not.\n> > +\t   When fetching branch1, the 40 commits get sent, the first\n> > +\t   is acknowledged as common, and the local head of branch2\n> > +\t   never gets sent.\n> > +\n> > +\t   As a consequence, the whole history of branch2\n> > +\t   (git-rev-list branch2 ^branch1) gets packed and transmitted.\n> \n> Arrrgggggggh.  The description above captures the essense of the\n> problem very well, but faking dates and still popping by recency\n> looks like a really ugly hack to me.\n\nIt is ugly. But it is a good heuristic. And the code is simple, because I \ncould use the existing functions for inserting into a commit_list.\n\n> Wouldn't it be cleaner if you traversed commits starting from\n> local refs, and assign distance from the tip of the branch to\n> each object (use generic object->util field for it), and\n> maintain an object_list that is sorted by depth, similar to\n> commit_list sorted by commit date?  Then you can pop from the\n> list by depth, closer to tip first, and tell the other end that\n> you have branch1, branch2, branch1^, branch2^, branch1~2,\n> branch2~1,...  which is the order the above situation benefits\n> from.\n\nI have an example from the real world why this is bad as well: I have a \nrepository imported from CVS, which has this silly CVS initial import \nmarked as it's own branch. This was long, long, long ago, but \ngit-cvsimport faithfully creates the branch \"initial\" for it anyway.\n\nImagine now the case that I added 40 revisions locally between the last \nfetch and now. What would happen is this:\n\nIn both cases, your git-fetch-pack and mine, the tips would get sent, the \n(very old one) \"initial\" acknowledged. A few of those 40 revisions would \nget sent, too, (and in your case, the root rev), but not at all the \noptimal merge base. In essence, almost all would get sent again.\n\nHow about this on top of your idea:\n\nSend only those branch{i}^n where n is a power of 2. This is a tradeoff \nbetween the speed we find sensible common revs, and the accurateness of \nthe best pick.\n\nNote that the best thing would probably be to add a binary search to that, \nand *not* stop at the first ack'ed rev, but rather count them, and stop at \nMAX_HAS.\n\nCiao,\nDscho\n"},{"id":"10431","messageId":"7vwtk6vlqz.fsf@assigned-by-dhcp.cox.net","threadId":"2174","inReplyTo":"Pine.LNX.4.63.0510211111440.4950@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-21T17:11:00Z","receivedAt":"2005-10-21T17:11:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Note that the best thing would probably be to add a binary search to that, \n> and *not* stop at the first ack'ed rev, but rather count them, and stop at \n> MAX_HAS.\n\nAnother alternative.\n\nWe send \"haves\" in order, without 2^n skipping nor binary search\nbacktrack.  Instead, add a logic in upload-pack to see if a\nnewly arrived \"have\" is a direct child of anything that we have\nalready heard about, and mark to ignore them.  We need to add\nthat MAX_HAS counting to fetch-pack side for this to work.\n\nThis is not even compile tested, but just to outline the idea.\n\n(... now off to day-job ...)\n\n---\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 8a41caf..d98a28e 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -3,9 +3,11 @@\n #include \"pkt-line.h\"\n #include \"tag.h\"\n #include \"object.h\"\n+#include \"commit.h\"\n \n static const char upload_pack_usage[] = \"git-upload-pack [--strict] [--timeout=nn] <dir>\";\n \n+#define THEY_HAVE (1U << 0)\n #define MAX_HAS (16)\n #define MAX_NEEDS (256)\n static int nr_has = 0, nr_needs = 0;\n@@ -92,6 +94,20 @@ static int got_sha1(char *hex, unsigned \n \t\treturn 0;\n \tnr = nr_has;\n \tif (nr < MAX_HAS) {\n+\t\tstruct object *o = lookup_object(sha1);\n+\t\tif (!o || (o->parsed || !parse_object(sha1)))\n+\t\t\tdie(\"oops\");\n+\t\tif (o->type == commit_type) {\n+\t\t\tstruct commit_list *parents;\n+\t\t\tif (o->flags & THEY_HAVE)\n+\t\t\t\treturn 0;\n+\t\t\to->flags |= THEY_HAVE;\n+\t\t\tfor (parents = ((struct commit*)o)->parents;\n+\t\t\t     parents;\n+\t\t\t     parents = parents->next) {\n+\t\t\t\tparents->item->object.flags |= THEY_HAVE;\n+\t\t\t}\n+\t\t}\n \t\tmemcpy(has_sha1[nr], sha1, 20);\n \t\tnr_has = nr+1;\n \t}\n@@ -104,6 +120,9 @@ static int get_common_commits(void)\n \tunsigned char sha1[20];\n \tint len;\n \n+\ttrack_object_refs = 0;\n+\tsave_commit_buffer = 0;\n+\n \tfor(;;) {\n \t\tlen = packet_read_line(0, line, sizeof(line));\n \t\treset_timeout();\n"},{"id":"10435","messageId":"Pine.LNX.4.63.0510212134570.5542@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"2174","inReplyTo":"7vwtk6vlqz.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-10-21T19:44:12Z","receivedAt":"2005-10-21T19:44:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 21 Oct 2005, Junio C Hamano wrote:\n\n> We send \"haves\" in order, without 2^n skipping nor binary search\n> backtrack.  Instead, add a logic in upload-pack to see if a\n> newly arrived \"have\" is a direct child of anything that we have\n> already heard about, and mark to ignore them.  We need to add\n> that MAX_HAS counting to fetch-pack side for this to work.\n\nYes. This makes it more simple, and is very efficient in the common case. \nHow about increasing MAX_HAS to 64?\n\nAdapted patch for fetch-pack coming soon.\n\nCiao,\nDscho\n"},{"id":"10437","messageId":"Pine.LNX.4.64.0510211618420.25300@iabervon.org","threadId":"2174","inReplyTo":"Pine.LNX.4.63.0510211111440.4950@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-10-21T20:25:20Z","receivedAt":"2005-10-21T20:25:20Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 21 Oct 2005, Johannes Schindelin wrote:\n\n> Hi,\n> \n> On Fri, 21 Oct 2005, Junio C Hamano wrote:\n> \n> > Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> > \n> > > +\t   Branch1 has 40 commits since it last merged with branch2,\n> > > +\t   and branch2 has 2 more commits since then.\n> > > +\n> > > +\t   On the other end, branch1 is up-to-date, but branch2 is not.\n> > > +\t   When fetching branch1, the 40 commits get sent, the first\n> > > +\t   is acknowledged as common, and the local head of branch2\n> > > +\t   never gets sent.\n> > > +\n> > > +\t   As a consequence, the whole history of branch2\n> > > +\t   (git-rev-list branch2 ^branch1) gets packed and transmitted.\n> > \n> > Arrrgggggggh.  The description above captures the essense of the\n> > problem very well, but faking dates and still popping by recency\n> > looks like a really ugly hack to me.\n> \n> It is ugly. But it is a good heuristic. And the code is simple, because I \n> could use the existing functions for inserting into a commit_list.\n\nThe existing functions aren't really very complicated. You could easily \nseparate out the pop and the adding of parents, and go first through a \nlist of tips and then through the date-sorted list of ancestors. And I \nthink that separation would be useful for some changes Linus was making to \nrev-list recently.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"10441","messageId":"Pine.LNX.4.63.0510212308060.8227@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"2174","inReplyTo":"Pine.LNX.4.64.0510211618420.25300@iabervon.org","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-10-21T21:08:54Z","receivedAt":"2005-10-21T21:08:54Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nhere comes a WIP on that patch (needs to be tested lots more):\n\n fetch-pack.c |  154 ++++++++++++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 117 insertions(+), 37 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 8566ab1..33ce435 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -13,18 +13,109 @@ static const char fetch_pack_usage[] =\n static const char *exec = \"git-upload-pack\";\n \n #define COMPLETE\t(1U << 0)\n+#define COMMON\t\t(1U << 1)\n+#define COMMON_REF\t(1U << 2 | COMMON)\n+#define SEEN\t\t(1U << 3)\n+#define POPPED\t\t(1U << 4)\n+#define MAX_HAS (16)\n+\n+static struct commit_list *rev_list = NULL;\n+static struct commit_list *rev_list_end = NULL;\n+static unsigned long non_common_revs = 0;\n+\n+static void rev_list_append(struct commit *commit, int mark)\n+{\n+\tif (!(commit->object.flags & mark)) {\n+\t\tcommit->object.flags |= mark;\n+\n+\t\tif (rev_list == NULL) {\n+\t\t\tcommit_list_insert(commit, &rev_list);\n+\t\t\trev_list_end = rev_list;\n+\t\t} else {\n+\t\t\tcommit_list_insert(commit, &(rev_list_end->next));\n+\t\t\trev_list_end = rev_list_end->next;\n+\t\t}\n+\n+\t\tif (!(commit->object.flags & COMMON))\n+\t\t\tnon_common_revs++;\n+\t}\n+}\n+\n+static int rev_list_append_sha1(const char *path, const unsigned char *sha1)\n+{\n+\tstruct object *o = deref_tag(parse_object(sha1));\n+\n+\tif (o->type == commit_type)\n+\t\trev_list_append((struct commit *)o, SEEN);\n+\n+\treturn 0;\n+}\n+\n+static void mark_common(struct object *o)\n+{\n+\tif (o != NULL && !(o->flags & COMMON)) {\n+\t\to->flags |= COMMON;\n+\t\tif (!(o->flags & SEEN))\n+\t\t\trev_list_append((struct commit *)o, SEEN);\n+\t\telse if (!(o->flags & POPPED))\n+\t\t\tnon_common_revs--;\n+\t}\n+}\n+\n+/*\n+  Get the next rev to send, ignoring the common.\n+*/\n+\n+static const unsigned char* get_rev()\n+{\n+\tstruct commit *commit = NULL;\n+\n+\twhile (commit == NULL) {\n+\t\tunsigned int mark;\n+\t\tstruct commit_list* parents;\n+\n+\t\tif (rev_list == NULL || non_common_revs == 0)\n+\t\t\treturn NULL;\n+\n+\t\tcommit = rev_list->item;\n+\t\tcommit->object.flags |= POPPED;\n+\t\tif (!(commit->object.flags & COMMON))\n+\t\t\tnon_common_revs--;\n+\t\t\n+\t\tparents = commit->parents;\n+\n+\t\tif (commit->object.flags & COMMON) {\n+\t\t\t/* do not send \"have\", and ignore ancestors */\n+\t\t\tcommit = NULL;\n+\t\t\tmark = COMMON | SEEN;\n+\t\t} else if (commit->object.flags & COMMON_REF)\n+\t\t\t/* send \"have\", and ignore ancestors */\n+\t\t\tmark = COMMON | SEEN;\n+\t\telse\n+\t\t\t/* send \"have\", also for its ancestors */\n+\t\t\tmark = SEEN;\n+\n+\t\twhile (parents) {\n+\t\t\tif (mark & COMMON)\n+\t\t\t\tmark_common((struct object *)parents->item);\n+\t\t\telse\n+\t\t\t\trev_list_append(parents->item, mark);\n+\t\t\tparents = parents->next;\n+\t\t}\n+\t}\n+\n+\treturn commit->object.sha1;\n+}\n \n static int find_common(int fd[2], unsigned char *result_sha1,\n \t\t       struct ref *refs)\n {\n \tint fetching;\n-\tstatic char line[1000];\n-\tstatic char rev_command[1024];\n-\tint count = 0, flushes = 0, retval, rev_command_len;\n-\tFILE *revs;\n+\tint count = 0, flushes = 0, ack_count = 0, retval;\n+\tconst unsigned char *sha1;\n+\n+\tfor_each_ref(rev_list_append_sha1);\n \n-\tstrcpy(rev_command, \"git-rev-list $(git-rev-parse --all)\");\n-\trev_command_len = strlen(rev_command);\n \tfetching = 0;\n \tfor ( ; refs ; refs = refs->next) {\n \t\tunsigned char *remote = refs->old_sha1;\n@@ -42,25 +133,15 @@ static int find_common(int fd[2], unsign\n \t\t */\n \t\tif (((o = lookup_object(remote)) != NULL) &&\n \t\t    (o->flags & COMPLETE)) {\n-\t\t\tstruct commit_list *p;\n-\t\t\tstruct commit *commit =\n-\t\t\t\t(struct commit *) (o = deref_tag(o));\n-\t\t\tif (!o)\n-\t\t\t\tgoto repair;\n-\t\t\tif (o->type != commit_type)\n-\t\t\t\tcontinue;\n-\t\t\tp = commit->parents;\n-\t\t\twhile (p &&\n-\t\t\t       rev_command_len + 44 < sizeof(rev_command)) {\n-\t\t\t\tsnprintf(rev_command + rev_command_len, 44,\n-\t\t\t\t\t \" ^%s\",\n-\t\t\t\t\t sha1_to_hex(p->item->object.sha1));\n-\t\t\t\trev_command_len += 43;\n-\t\t\t\tp = p->next;\n-\t\t\t}\n+\t\t\to = deref_tag(o);\n+\n+\t\t\tif (o->type == commit_type)\n+\t\t\t\trev_list_append((struct commit *)o,\n+\t\t\t\t\t\tCOMMON_REF | SEEN);\n+\n \t\t\tcontinue;\n \t\t}\n-\trepair:\n+\n \t\tpacket_write(fd[1], \"want %s\\n\", sha1_to_hex(remote));\n \t\tfetching++;\n \t}\n@@ -68,21 +149,16 @@ static int find_common(int fd[2], unsign\n \tif (!fetching)\n \t\treturn 1;\n \n-\trevs = popen(rev_command, \"r\");\n-\tif (!revs)\n-\t\tdie(\"unable to run 'git-rev-list'\");\n-\n \tflushes = 1;\n \tretval = -1;\n-\twhile (fgets(line, sizeof(line), revs) != NULL) {\n-\t\tunsigned char sha1[20];\n-\t\tif (get_sha1_hex(line, sha1))\n-\t\t\tdie(\"git-fetch-pack: expected object name, got crud\");\n+\twhile ((sha1 = get_rev())) {\n \t\tpacket_write(fd[1], \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (verbose)\n \t\t\tfprintf(stderr, \"have %s\\n\", sha1_to_hex(sha1));\n \t\tif (!(31 & ++count)) {\n \t\t\tpacket_flush(fd[1]);\n+\t\t\tif (verbose)\n+\t\t\t\tfprintf(stderr, \"flush\\n\");\n \t\t\tflushes++;\n \n \t\t\t/*\n@@ -92,16 +168,19 @@ static int find_common(int fd[2], unsign\n \t\t\tif (count == 32)\n \t\t\t\tcontinue;\n \t\t\tif (get_ack(fd[0], result_sha1)) {\n-\t\t\t\tflushes = 0;\n-\t\t\t\tretval = 0;\n+\t\t\t\tmark_common(lookup_object(result_sha1));\n \t\t\t\tif (verbose)\n-\t\t\t\t\tfprintf(stderr, \"got ack\\n\");\n-\t\t\t\tbreak;\n+\t\t\t\t\tfprintf(stderr, \"got ack %s\\n\",\n+\t\t\t\t\t\t\tsha1_to_hex(result_sha1));\n+\t\t\t\tif (++ack_count > MAX_HAS) {\n+\t\t\t\t\tflushes = 0;\n+\t\t\t\t\tretval = 0;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t\tflushes--;\n \t\t}\n \t}\n-\tpclose(revs);\n \tpacket_write(fd[1], \"done\\n\");\n \tif (verbose)\n \t\tfprintf(stderr, \"done\\n\");\n@@ -109,7 +188,8 @@ static int find_common(int fd[2], unsign\n \t\tflushes--;\n \t\tif (get_ack(fd[0], result_sha1)) {\n \t\t\tif (verbose)\n-\t\t\t\tfprintf(stderr, \"got ack\\n\");\n+\t\t\t\tfprintf(stderr, \"got ack %s\\n\",\n+\t\t\t\t\tsha1_to_hex(result_sha1));\n \t\t\treturn 0;\n \t\t}\n \t}\n"},{"id":"10442","messageId":"7vbr1iv9nz.fsf@assigned-by-dhcp.cox.net","threadId":"2174","inReplyTo":"Pine.LNX.4.63.0510212134570.5542@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-10-21T21:32:00Z","receivedAt":"2005-10-21T21:32:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Yes. This makes it more simple, and is very efficient in the common case. \n> How about increasing MAX_HAS to 64?\n\nThe other day I saw HPA tried to sneak in a change to increase\nit to 64, mingled with other changes.  I think increasing it\nmakes sense.\n\nNow the question is, if we count MAX_HAS on the fetch-pack side,\nhow would we coordinate that value with the real limit the other\nend uses.  I guess that would not matter too much.  It would not\naffect the correctness anyway.\n"},{"id":"10448","messageId":"Pine.LNX.4.63.0510220223100.13270@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"2174","inReplyTo":"7vbr1iv9nz.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Do not call git-rev-list from git-fetch-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-10-22T00:35:42Z","receivedAt":"2005-10-22T00:35:42Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 21 Oct 2005, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > Yes. This makes it more simple, and is very efficient in the common case. \n> > How about increasing MAX_HAS to 64?\n> \n> The other day I saw HPA tried to sneak in a change to increase\n> it to 64, mingled with other changes.  I think increasing it\n> makes sense.\n\nAgree.\n\nHowever, I do not see a way for upload-pack to force fetch-pack to send \n\"have\" lines. Maybe this would be an important change to the protocol? I \nimagine that I could craft a custom fetch-pack which DoS'es any \ncurrent upload-pack.\n\n> Now the question is, if we count MAX_HAS on the fetch-pack side,\n> how would we coordinate that value with the real limit the other\n> end uses.  I guess that would not matter too much.  It would not\n> affect the correctness anyway.\n\nReally, there should be a way for upload-pack to say that enough is \nenough, and it wants to send the pack now.\n\nCiao,\nDscho\n"}]}