{"thread":{"id":"4277","subject":"Slow fetches of tags","startedAt":"2006-05-24T13:10:22Z","lastAt":"2006-07-29T12:47:03Z","messageCount":23,"participants":["Ralf Baechle","Linus Torvalds","Junio C Hamano","Johannes Schindelin","Nguyễn Thái Ngọc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"20625","messageId":"20060524131022.GA11449@linux-mips.org","threadId":"4277","inReplyTo":null,"subject":"Slow fetches of tags","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2006-05-24T13:10:22Z","receivedAt":"2006-05-24T13:10:22Z","isPatch":false,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"I have a fairly large git tree (with a 320MB pack file containing some\n700,000 objects).  A small fetch like\n\n  git fetch git://www.kernel.org/pub/scm/linux/kernel/git/stable/\\\n       linux-2.6.16.y.git master:v2.6.16-stable\n\nwhich only fetches a handful of objects (v2.6.16.17 -> v2.6.16.18) will\ntake on the order of 4-5 minutes.  Adding the \"-n\" option is will bring\nthe operation down to under a second, so it really is just the tags\nthat are slowing things down so much..\n\n  Ralf\n"},{"id":"20635","messageId":"Pine.LNX.4.64.0605240931480.5623@g5.osdl.org","threadId":"4277","inReplyTo":"20060524131022.GA11449@linux-mips.org","subject":"Re: Slow fetches of tags","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-24T16:45:29Z","receivedAt":"2006-05-24T16:45:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 24 May 2006, Ralf Baechle wrote:\n>\n> I have a fairly large git tree (with a 320MB pack file containing some\n> 700,000 objects).  A small fetch like\n> \n>   git fetch git://www.kernel.org/pub/scm/linux/kernel/git/stable/\\\n>        linux-2.6.16.y.git master:v2.6.16-stable\n> \n> which only fetches a handful of objects (v2.6.16.17 -> v2.6.16.18) will\n> take on the order of 4-5 minutes.  Adding the \"-n\" option is will bring\n> the operation down to under a second, so it really is just the tags\n> that are slowing things down so much..\n\nSo this is a tree where you already _have_ most of the tags, no?\n\nCan you add a printout to show what the \"taglist\" is for you in \ngit-fetch.sh (just before the thing that does that\n\n\tfetch_main \"$taglist\"\n\nthing?). It _should_ have pruned out all the tags you already have.\n\nOr is it just the \"git-ls-remote\" that takes forever? (Or, if you run \n\"top\", is there something that is an obviously heavy operation on the \nclient side?)\n\n\t\tLinus\n"},{"id":"20637","messageId":"Pine.LNX.4.64.0605240947580.5623@g5.osdl.org","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605240931480.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-24T17:21:41Z","receivedAt":"2006-05-24T17:21:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 24 May 2006, Linus Torvalds wrote:\n> \n> Can you add a printout to show what the \"taglist\" is for you in \n> git-fetch.sh (just before the thing that does that\n> \n> \tfetch_main \"$taglist\"\n> \n> thing?). It _should_ have pruned out all the tags you already have.\n\nActually, looking at that tag-fetching logic, we already know that we have \nthe objects that the tags point to (because those are the only kinds that \nwe should auto-follow). I wonder if the slowness is because of all the \nhave/want commit following, which walks the whole tree to say \"I have \nthis\", when in this case we really should directly say \"I have these\" for \nthe objects that the tags point to.\n\nSo the problem may be that we basically send a totally unnecessary list of \nall the objects we have, when the other end really only cares about the \nfact that we have the objects that the tags point to. Which we know we do, \nbut we didn't say so, because \"git-fetch\" didn't really mark them that \nway.\n\nAnd instead of sending the commits that we know we have, and that we know \nare the interesting ones and that will cut off the tag-object-walk, we \nstart from all the local tips, and use the regular \"parse commits in date \norder\" thing and send \"have\" lines for everything we see that isn't \ncommon. Walking a lot of unnecessary crud.\n\nJunio? Any ideas? I didn't want to do that tag-auto-following, and while I \nadmit it's damn convenient, it's really quite broken, methinks. \n\nI almost suspect that we need to have a syntax where-by the local \nfetch-list ends up doing\n\n\t\"$tagname:$tagname:$sha1wehave\"\n\nas the argument to fetch-pack, and then fetch-pack would be modified to \nsend those \"$sha1wehave\" objects early as \"have\" objects. Ie start from \nsomething like\n\n\tdiff --git a/git-fetch.sh b/git-fetch.sh\n\tindex 280f62e..dce3812 100755\n\t--- a/git-fetch.sh\n\t+++ b/git-fetch.sh\n\t@@ -400,7 +400,7 @@ case \"$no_tags$tags\" in\n\t \t\t\t}\n\t \t\t\tgit-cat-file -t \"$sha1\" >/dev/null 2>&1 || continue\n\t \t\t\techo >&2 \"Auto-following $name\"\n\t-\t\t\techo \".${name}:${name}\"\n\t+\t\t\techo \".${name}:${name}:${sha1}\"\n\t \t\tdone)\n\t \tesac\n\t \tcase \"$taglist\" in\n\nand then pass the info all the way up (the above patch will obviously \nresult in a totally broken script, everything downstream from that point \nwould have to be taught about the \"already have this\" part too).\n\nRalf, which repo is this, so that others (me, if I get the time and \nenergy, Junio or some other hapless sucker^W^Whero if I'm lucky) can try \nthings out?\n\n\t\tLinus\n"},{"id":"20638","messageId":"20060524180813.GA32519@linux-mips.org","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605240931480.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2006-05-24T18:08:13Z","receivedAt":"2006-05-24T18:08:13Z","isPatch":false,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"On Wed, May 24, 2006 at 09:45:29AM -0700, Linus Torvalds wrote:\n\n> So this is a tree where you already _have_ most of the tags, no?\n\nYes, git did end up only fetching v2.6.16.18 as the single tag.\n\n> Can you add a printout to show what the \"taglist\" is for you in \n> git-fetch.sh (just before the thing that does that\n> \n> \tfetch_main \"$taglist\"\n> \n> thing?). It _should_ have pruned out all the tags you already have.\n\nRight, it's just \"refs/tags/v2.6.16.18:refs/tags/v2.6.16.18\".\n\n> Or is it just the \"git-ls-remote\" that takes forever?\n\ngit-ls-remote git://www.kernel.org/pub/scm/linux/kernel/git/stable/\\\nlinux-2.6.16.y takes about 1.5s.\n\n> (Or, if you run \n> \"top\", is there something that is an obviously heavy operation on the \n> client side?)\n\ngit-fetch-pack was burning some 6min CPU.  Nothing else even even shows\nup on the \"top\" radar.\n\nAnother funny thing I noticed in top is that the git-fetch-pack arguments\ngot overwritten:\n\n$ cat /proc/1702/cmdline | tr '\\0' ' '\ngit-fetch-pack --thin git //www.kernel.org pub/scm/linux/kernel/git/stable/linux-2.6.16.y.git  efs/heads/master  efs/tags/v2.6.16.18\n\nGuess that doesn't matter.  Anyway, so I ran strace on this git-fetch-pack\ninvocation:\n\n[...]\nmunmap(0xb7fe5000, 229)                 = 0\ngetdents(5, /* 0 entries */, 4096)      = 0\nclose(5)                                = 0\ngetdents(4, /* 0 entries */, 4096)      = 0\nclose(4)                                = 0\nwrite(3, \"0046want 9b549d8e1e2f16cffbb414a\"..., 70) = 70\nwrite(3, \"0000\", 4)                     = 4\nwrite(3, \"0032have 0bcf7932d0ea742e765a40b\"..., 50) = 50\nwrite(3, \"0032have 54e938a80873e85f9c02ab4\"..., 50) = 50\nwrite(3, \"0032have 2d0a9369c540519bab8018e\"..., 50) = 50\nwrite(3, \"0032have bf3060065ef9f0a8274fc32\"..., 50) = 50\nwrite(3, \"0032have 27602bd8de8456ac619b77c\"..., 50) = 50\n[... another 42,000+ similar lines chopped off ...]\n\n9b549d8e1e2f16cffbb414a is Chris Wright's tag for v2.6.16.18.  So far,\nas expected.\n\nAnd this is where things are getting interesting:\n\n$ git-name-rev 0bcf7932d0ea742e765a40b\n0bcf7932d0ea742e765a40b master\n$ git-name-rev 54e938a80873e85f9c02ab4\n54e938a80873e85f9c02ab4 34k-2.6.16.18\n$ git-name-rev 2d0a9369c540519bab8018e\n2d0a9369c540519bab8018e 34k-2.6.16.18~1\n$ git-name-rev bf3060065ef9f0a8274fc32\nbf3060065ef9f0a8274fc32 34k-2.6.16.18~2\n$ git-name-rev 27602bd8de8456ac619b77c\n27602bd8de8456ac619b77c 34k-2.6.16.18~3\n\nIt's sending every object back to the start of history ...\n\n  Ralf\n"},{"id":"20639","messageId":"7v64jv8fdx.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605240947580.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-24T18:08:26Z","receivedAt":"2006-05-24T18:08:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> So the problem may be that we basically send a totally unnecessary list of \n> all the objects we have, when the other end really only cares about the \n> fact that we have the objects that the tags point to. Which we know we do, \n> but we didn't say so, because \"git-fetch\" didn't really mark them that \n> way.\n\nI think this speculation is correct.  We should be able to do\nbetter.\n\n> I almost suspect that we need to have a syntax where-by the local \n> fetch-list ends up doing\n>\n> \t\"$tagname:$tagname:$sha1wehave\"\n>\n> as the argument to fetch-pack, and then fetch-pack would be modified to \n> send those \"$sha1wehave\" objects early as \"have\" objects.\n\nBut this logic has to be a bit more involved.\n\nA \"have\" object is not just has_sha1_file(), but it needs to be\nreachable from one of our tips we have already verified as\ncomplete, so either the caller of fetch-pack does the\nverification and give a verified $sha1wehave, or fetch-pack\ntakes $sha1weseemtohave and does its own verification and then\nsend it as one of the \"have\" objects (the issue is the same as\nthe one in my previous message to Eric W. Biederman -- we trust\nonly refs not just having a single object).\n\nIt might be useful to have a helper script you can give N object\nnames and M refs (and/or --all flag to mean \"all of the refs\"),\nwhich returns the ones that are reachable from the given refs.\nIt would be even more useful if it were a helper function, but\ngiven that the computation would involve walking the ancestry\nchain, I suspect it would have a bad interaction with any user\nof such a helper function that wants to do its own ancestry\nwalking, because many of them seem to assume an object that has\nalready been parsed are the ones they parsed for their own\npurpose.\n"},{"id":"20641","messageId":"7vslmz6zah.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"20060524180813.GA32519@linux-mips.org","subject":"Re: Slow fetches of tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-24T18:41:26Z","receivedAt":"2006-05-24T18:41:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ralf Baechle <ralf@linux-mips.org> writes:\n\n>> Or is it just the \"git-ls-remote\" that takes forever?\n>\n> git-ls-remote git://www.kernel.org/pub/scm/linux/kernel/git/stable/\\\n> linux-2.6.16.y takes about 1.5s.\n\nGood; that is as expected.  ls-remote over git protocol just\ngets the initial \"have\" lines from the upload-pack and exits,\nand there is no handshaking.\n\n> Another funny thing I noticed in top is that the git-fetch-pack arguments\n> got overwritten:\n>\n> $ cat /proc/1702/cmdline | tr '\\0' ' '\n> git-fetch-pack --thin git //www.kernel.org pub/scm/linux/kernel/git/stable/linux-2.6.16.y.git  efs/heads/master  efs/tags/v2.6.16.18\n>\n> Guess that doesn't matter.\n\nThis is also expected - fetch-pack (connect.c::path_match(), actually) \nsmudges the list of refs to remember which ones the caller asked\nare going to be fulfilled and which ones are not.  Not the most\nbeautiful part of the code ;-).\n\n> Guess that doesn't matter.  Anyway, so I ran strace on this git-fetch-pack\n> invocation:\n>\n> [...]\n> munmap(0xb7fe5000, 229)                 = 0\n> getdents(5, /* 0 entries */, 4096)      = 0\n> close(5)                                = 0\n> getdents(4, /* 0 entries */, 4096)      = 0\n> close(4)                                = 0\n> write(3, \"0046want 9b549d8e1e2f16cffbb414a\"..., 70) = 70\n> write(3, \"0000\", 4)                     = 4\n> write(3, \"0032have 0bcf7932d0ea742e765a40b\"..., 50) = 50\n> write(3, \"0032have 54e938a80873e85f9c02ab4\"..., 50) = 50\n> write(3, \"0032have 2d0a9369c540519bab8018e\"..., 50) = 50\n> write(3, \"0032have bf3060065ef9f0a8274fc32\"..., 50) = 50\n> write(3, \"0032have 27602bd8de8456ac619b77c\"..., 50) = 50\n> [... another 42,000+ similar lines chopped off ...]\n>\n> 9b549d8e1e2f16cffbb414a is Chris Wright's tag for v2.6.16.18.  So far,\n> as expected.\n>\n> And this is where things are getting interesting:\n>\n> $ git-name-rev 0bcf7932d0ea742e765a40b\n> 0bcf7932d0ea742e765a40b master\n> $ git-name-rev 54e938a80873e85f9c02ab4\n> 54e938a80873e85f9c02ab4 34k-2.6.16.18\n> $ git-name-rev 2d0a9369c540519bab8018e\n> 2d0a9369c540519bab8018e 34k-2.6.16.18~1\n> $ git-name-rev bf3060065ef9f0a8274fc32\n> bf3060065ef9f0a8274fc32 34k-2.6.16.18~2\n> $ git-name-rev 27602bd8de8456ac619b77c\n> 27602bd8de8456ac619b77c 34k-2.6.16.18~3\n>\n> It's sending every object back to the start of history ...\n\nIs this \"master\" commit 0bcf79 part of v2.6.16.18 history?  If\nnot, how diverged are you?  That is, what does this command tell\nyou?\n\n\tgit rev-list b7d0617..master | wc -l\n\nHere, b7d0617 is the name of the commit object that is pointed\nby v2.6.16.18 tag.\n"},{"id":"20643","messageId":"7vhd3f6y4v.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605240947580.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-24T19:06:24Z","receivedAt":"2006-05-24T19:06:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Junio? Any ideas? I didn't want to do that tag-auto-following, and while I \n> admit it's damn convenient, it's really quite broken, methinks. \n\nI think the current setup is broken on two counts.  If you fetch\nwithout remote tracking branch, I suspect that we end up asking\nfor the tip of the remote again -- because there is no ref that\nsays \"this commit is known to be complete -- we just fetched\nfrom them successfully\".\n\nBut I think what Ralf is seeing is a bit different.  The example\ngiven:\n\n  git fetch git://git.kernel.org/pub/scm/linux/kernel/git/stable/\\\n       linux-2.6.16.y.git master:v2.6.16-stable\n\ndoes use a tracking branch, and when the tag following kicks in,\nv2.6.16-stable head should have been updated.  I suspect it is\njust its head commit is older than tips of other branches, and\npurely date based sorting done by fetch-pack.c::get_rev() ends\nup walking them before it gets to the tip of the branch we just\nfetched.\n\nI wonder if we can do a dirty hack to give bias to commits\ncoming from refs that are newer (on the local filesystem -- that\nis, mtime of .git/refs/heads/v2.6.16-stable must be a lot newer\nthan .git/refs/heads/master in this case because we just fetched\nit)...\n"},{"id":"20645","messageId":"Pine.LNX.4.64.0605241200110.5623@g5.osdl.org","threadId":"4277","inReplyTo":"7v64jv8fdx.fsf@assigned-by-dhcp.cox.net","subject":"Re: Slow fetches of tags","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-24T19:17:36Z","receivedAt":"2006-05-24T19:17:36Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 24 May 2006, Junio C Hamano wrote:\n> \n> A \"have\" object is not just has_sha1_file(), but it needs to be\n> reachable from one of our tips we have already verified as\n> complete\n\nYou're right.\n\nAnd the strange part is that the commit we should give for the tag thing \n_should_ actually be pretty recent, and I wonder why we end up walking the \nwhole damn tree history and saying \"want\" to basically them all. \n\nIOW, I think there's something more fundamentally wrong with the tag \nfollowing. We _should_ have figured out much more quickly that we have it \nall.\n\nI'm starting to suspect that it's actually a tag-specific problem: we do \nthat reachability crud all by commit history, so the tags are a total \nspecial case, and if we don't send the proper HAVE/WANT for those or mark \nthem properly with THEY_HAVE/COMMON etc, maybe the algorithm just gets \nconfused.\n\nI need to go pick up my youngest, so I'll be off-line on this for a while. \nWill try to think it through.\n\n\t\tLinus\n"},{"id":"20655","messageId":"Pine.LNX.4.64.0605241641250.5623@g5.osdl.org","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605241200110.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-24T23:43:02Z","receivedAt":"2006-05-24T23:43:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 24 May 2006, Linus Torvalds wrote:\n> \n> IOW, I think there's something more fundamentally wrong with the tag \n> following. We _should_ have figured out much more quickly that we have it \n> all.\n\nActually, maybe the problem is that Ralf's tree has two roots, because of \nthe old CVS history. It might be following the other root down for the \n\"have\" part, since that one doesn't exist at all in the target and the \nother side will never acknowledge any of it. \n\nI'll play with it.\n\n\t\tLinus\n"},{"id":"20659","messageId":"7vd5e23n5a.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605241641250.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-25T01:32:01Z","receivedAt":"2006-05-25T01:32:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Wed, 24 May 2006, Linus Torvalds wrote:\n>> \n>> IOW, I think there's something more fundamentally wrong with the tag \n>> following. We _should_ have figured out much more quickly that we have it \n>> all.\n>\n> Actually, maybe the problem is that Ralf's tree has two roots, because of \n> the old CVS history. It might be following the other root down for the \n> \"have\" part, since that one doesn't exist at all in the target and the \n> other side will never acknowledge any of it. \n>\n> I'll play with it.\n\nI think I know what is going on.  You are exactly right -- the\ntwo-root ness is what is causing this.\n\nWe used to stop sending \"have\" immediately after we get an ACK.\nThis was troublesome for trees with many long branches, so we\nintroduced multi_ack protocol extension to let the server side\n(upload-pack) say \"Ok, enough on this branch -- I know this\nobject so do not tell me any more about objects reachable from\nit, but do tell me about other development tracks if you have\none\".  If you run \"fetch-pack -v\" after priming a repository\nwith Ralf's tree and Chris's tree, you will see many \"have\" with\noccasional \"got ack 2 [0-9a-f]{40}\".  The latter is upload-pack\nacking this way.\n\nThis was done to prevent already-known-to-be-common objects\nfilling up the list of known common commits on the server side.\nThe remaining slots can be used to discover common commits on\nother branches, so that we can minimize the transfer.  It was an\nimportant optimization when dealing with sets of branches that\nare long.\n\nThis unfortunately breaks down quite badly in this case, since\nthe remaining \"branch\" it keeps following is the other history\nChris's tree has never heard of down to its root in vain.\n\nIt might be worth changing fetch-pack to note that it has sent\nmany \"have\"s after it got an \"continue\" ACK, and give up early,\nsay using a heuristic between the age of the commit that did got\nan ACK and the one we are about to send out as a \"have\".\n"},{"id":"20667","messageId":"7vd5e21zh9.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"7vd5e23n5a.fsf@assigned-by-dhcp.cox.net","subject":"Re: Slow fetches of tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-25T04:48:34Z","receivedAt":"2006-05-25T04:48:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> It might be worth changing fetch-pack to note that it has sent\n> many \"have\"s after it got an \"continue\" ACK, and give up early,\n> say using a heuristic between the age of the commit that did got\n> an ACK and the one we are about to send out as a \"have\".\n\nI think the right fix for this is to change upload-pack to\ntraverse reachability chain from the \"want\" heads as it gets\n\"have\" from the downloader, and stop responding \"continue\" when\nall \"want\" heads can reach some \"have\" commits.  This would not\nprevent it from going down all the way to the root commit if\nwhat is wanted does not have anything to do with what the other\nend has (e.g. if you have only my main project branches, and you\nask for html head for the first time), but it would have\nprevented Ralf's tree from getting \"continue\" after he asked\nonly for v2.6.16.18 tag and said he has 2.6.16.18 commit and its\nancestors.  It should not be too difficult to do this, but here\nis an alternative, client-side workaround.\n\n-- >8 --\n[PATCH] fetch-pack: give up after getting too many \"ack continue\"\n\nIf your repository have more roots than the remote repository\nyou ask an object for, the remote upload-pack keeps responding\n\"ack continue\" until it fills up its received-have buffer\n(currently 256 entries).  Usually this is not a problem because\nthe requester stops traversing the ancestry chain from the commit\nit gets \"ack continue\" for, but this mechanism does not work as\na roadblock when it traverses down the path to the root the\nother side does not have.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 8daa93d..8371348 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -18,6 +18,12 @@ #define COMMON_REF\t(1U << 2)\n #define SEEN\t\t(1U << 3)\n #define POPPED\t\t(1U << 4)\n \n+/*\n+ * After sending this many \"have\"s if we do not get any new ACK , we\n+ * give up traversing our history.\n+ */\n+#define MAX_IN_VAIN 256\n+\n static struct commit_list *rev_list = NULL;\n static int non_common_revs = 0, multi_ack = 0, use_thin_pack = 0;\n \n@@ -134,6 +140,8 @@ static int find_common(int fd[2], unsign\n \tint fetching;\n \tint count = 0, flushes = 0, retval;\n \tconst unsigned char *sha1;\n+\tunsigned in_vain = 0;\n+\tint got_continue = 0;\n \n \tfor_each_ref(rev_list_insert_ref);\n \n@@ -172,6 +180,7 @@ static int find_common(int fd[2], unsign\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\tin_vain++;\n \t\tif (!(31 & ++count)) {\n \t\t\tint ack;\n \n@@ -200,9 +209,16 @@ static int find_common(int fd[2], unsign\n \t\t\t\t\t\tlookup_commit(result_sha1);\n \t\t\t\t\tmark_common(commit, 0, 1);\n \t\t\t\t\tretval = 0;\n+\t\t\t\t\tin_vain = 0;\n+\t\t\t\t\tgot_continue = 1;\n \t\t\t\t}\n \t\t\t} while (ack);\n \t\t\tflushes--;\n+\t\t\tif (got_continue && MAX_IN_VAIN < in_vain) {\n+\t\t\t\tif (verbose)\n+\t\t\t\t\tfprintf(stderr, \"giving up\\n\");\n+\t\t\t\tbreak; /* give up */\n+\t\t\t}\n \t\t}\n \t}\n done:\n"},{"id":"20680","messageId":"20060525131241.GA8443@linux-mips.org","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0605241641250.5623@g5.osdl.org","subject":"Re: Slow fetches of tags","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2006-05-25T13:12:41Z","receivedAt":"2006-05-25T13:12:41Z","isPatch":false,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"On Wed, May 24, 2006 at 04:43:02PM -0700, Linus Torvalds wrote:\n\n> Actually, maybe the problem is that Ralf's tree has two roots, because of \n> the old CVS history. It might be following the other root down for the \n> \"have\" part, since that one doesn't exist at all in the target and the \n> other side will never acknowledge any of it. \n> \n> I'll play with it.\n\nInteresting idea, so I went to play with it, too.  I took a copy of the\ntree and deleted all branches except the v2.6.16-stable tracking branch\nwhich I pruned back to v2.6.16.17, then added a new branch starting at\nthe oldest commit, your initial import of the kernel tree:\n\n$ git branch junk 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n$ git checkout junk\n$ seq -f \"%05.0f\" 1 100 | while read i; do echo $i; echo $i > Makefile;\\\n  git commit -s -m \"Blah $i\" Makefile; done\n\nSo with this I get:\n\n$ git branch\n* junk\n  v2.6.16-stable\n$\n\nIf I now run\n\n$ strace git-fetch-pack --thin git://www.kernel.org/pub/scm/linux/kernel/\\\n\tgit/stable/linux-2.6.16.y.git \\\n\trefs/heads/master refs/tags/v2.6.16.18 2>&1 | grep have /tmp/xxx\n\nI get:\n\nwrite(3, \"0032have ef686028603c291ba510c66\"..., 50) = 50\nwrite(3, \"0032have 150384dac99eb263c4385c7\"..., 50) = 50\nwrite(3, \"0032have 4df3afbfc2d8f6c22d41c63\"..., 50) = 50\n...\nwrite(3, \"0032have db119fba3d9495aa9cd5a63\"..., 50) = 50\n\nWhere ef686028603c291ba510c66 = junk, 150384dac99eb263c4385c7 = junk~1 ...\ndb119fba3d9495aa9cd5a63 = junk~99 (first commit on the junk branch).\n100 \"have\" lines upto this point, then:\n\nwrite(3, \"0032have d87319c3e4d908e157a462d\"..., 50) = 50\nwrite(3, \"0032have 22ddf44d54d0b2326f7b233\"..., 50) = 50\nwrite(3, \"0032have 90a03936acb1c3400a5833c\"..., 50) = 50\nwrite(3, \"0032have bf7d8bacaaf241a0f015798\"..., 50) = 50\nwrite(3, \"0032have a120571fbdfc8f543eea642\"..., 50) = 50\nwrite(3, \"0032have 42a46c74c4520174b82a60a\"..., 50) = 50\nwrite(3, \"0032have f66ab685594d49e570b2176\"..., 50) = 50\nwrite(3, \"0032have 834f514019e01f87657a257\"..., 50) = 50\nwrite(3, \"0032have 9d395d1961a0eeb9e8b1ef2\"..., 50) = 50\nwrite(3, \"0032have aa48603d1ba772d0a2b28ab\"..., 50) = 50\nwrite(3, \"0032have 54e5705fd460c7621a4d73c\"..., 50) = 50\nwrite(3, \"0032have 37863c8a9b7b0261ec76daa\"..., 50) = 50\nwrite(3, \"0032have a7603f9099869f9aeebd6c7\"..., 50) = 50\nwrite(3, \"0032have 623c30d2ae22cd4b8703c77\"..., 50) = 50\nwrite(3, \"0032have e2c78fb27dd13ab8c778a96\"..., 50) = 50\nwrite(3, \"0032have dbb676d1214c181e6cde4ce\"..., 50) = 50\nwrite(3, \"0032have 1ffe5e06461f72b9b6a2569\"..., 50) = 50\n\nThese are the commits for which this test tree has the tags left:\n\n$ ls .git/refs/tags/\nv2.6.16.1   v2.6.16.12  v2.6.16.15  v2.6.16.2  v2.6.16.5  v2.6.16.8\nv2.6.16.10  v2.6.16.13  v2.6.16.16  v2.6.16.3  v2.6.16.6  v2.6.16.9\nv2.6.16.11  v2.6.16.14  v2.6.16.17  v2.6.16.4  v2.6.16.7\n$\n\nAnd finally:\n\nwrite(3, \"0032have 1da177e4c3f41524e886b7f\"..., 50) = 50\n\nwhich is your Linux-2.6.12-rc2 import.\n\n  Ralf\n"},{"id":"20681","messageId":"20060525132746.GA30476@linux-mips.org","threadId":"4277","inReplyTo":"7vslmz6zah.fsf@assigned-by-dhcp.cox.net","subject":"Re: Slow fetches of tags","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2006-05-25T13:27:46Z","receivedAt":"2006-05-25T13:27:46Z","isPatch":false,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"On Wed, May 24, 2006 at 11:41:26AM -0700, Junio C Hamano wrote:\n\n> > $ git-name-rev 0bcf7932d0ea742e765a40b\n> > 0bcf7932d0ea742e765a40b master\n> > $ git-name-rev 54e938a80873e85f9c02ab4\n> > 54e938a80873e85f9c02ab4 34k-2.6.16.18\n> > $ git-name-rev 2d0a9369c540519bab8018e\n> > 2d0a9369c540519bab8018e 34k-2.6.16.18~1\n> > $ git-name-rev bf3060065ef9f0a8274fc32\n> > bf3060065ef9f0a8274fc32 34k-2.6.16.18~2\n> > $ git-name-rev 27602bd8de8456ac619b77c\n> > 27602bd8de8456ac619b77c 34k-2.6.16.18~3\n> >\n> > It's sending every object back to the start of history ...\n> \n> Is this \"master\" commit 0bcf79 part of v2.6.16.18 history?  If\n> not, how diverged are you?  That is, what does this command tell\n> you?\n\nNo, the master branch is where the MIPS development happens and it's\ntracking Linus' master branch.  The fact that I'm talking about this\nin context of -stable / v2.6.16.18 is that I started looking into why\nthings were taking minutes when doing a small fetch from 2.6.16-stable.\nIt happens just as well with Linus' tree or yet others like Matthias\nUrlich's -mm git tree.\n\n> \tgit rev-list b7d0617..master | wc -l\n> \n> Here, b7d0617 is the name of the commit object that is pointed\n> by v2.6.16.18 tag.\n\n$ git rev-list b7d0617..master | wc -l\n12845\n$ git rev-list master..b7d0617 | wc -l\t\t(that is swapped arguments)\n173\n$\n\n  Ralf\n"},{"id":"20758","messageId":"20060526154239.GA20839@linux-mips.org","threadId":"4277","inReplyTo":"7vd5e21zh9.fsf@assigned-by-dhcp.cox.net","subject":"Re: Slow fetches of tags","fromName":"Ralf Baechle","fromEmail":"ralf@linux-mips.org","sentAt":"2006-05-26T15:42:39Z","receivedAt":"2006-05-26T15:42:39Z","isPatch":false,"sender":{"key":"ralf@linux-mips.org","avatar":null},"body":"On Wed, May 24, 2006 at 09:48:34PM -0700, Junio C Hamano wrote:\n\n> I think the right fix for this is to change upload-pack to\n> traverse reachability chain from the \"want\" heads as it gets\n> \"have\" from the downloader, and stop responding \"continue\" when\n> all \"want\" heads can reach some \"have\" commits.  This would not\n> prevent it from going down all the way to the root commit if\n> what is wanted does not have anything to do with what the other\n> end has (e.g. if you have only my main project branches, and you\n> ask for html head for the first time), but it would have\n> prevented Ralf's tree from getting \"continue\" after he asked\n> only for v2.6.16.18 tag and said he has 2.6.16.18 commit and its\n> ancestors.  It should not be too difficult to do this, but here\n> is an alternative, client-side workaround.\n> \n> -- >8 --\n> [PATCH] fetch-pack: give up after getting too many \"ack continue\"\n\nSo I did test your patch.  In the big, slow repository it cuts down the\ntime for a\n\n  git fetch git://www.kernel.org/pub/scm/linux/kernel/git/stable/linux-2.6.16.y.git master:v2.6.16-stable\n\nfrom like 6min to about 7s.\n\nThanks!\n\n  Ralf\n"},{"id":"20770","messageId":"7vfyiwi4xl.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"20060526154239.GA20839@linux-mips.org","subject":"[PATCH/RFC] upload-pack: stop \"ack continue\" when we know common commits for wanted refs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-27T02:20:54Z","receivedAt":"2006-05-27T02:20:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When the downloader's repository has more roots than the server\nside has, the \"have\" exchange to figure out recent common\ncommits ends up traversing the whole history of branches that\nonly exist on the downloader's side.  When the downloader is\nasking for newer commits on the branch that exists on both ends,\nthis is totally unnecessary.\n\nThis adds logic to the server side to see if the wanted refs can\nreach the \"have\" commits received so far, and stop issuing \"ack\ncontinue\" once all of them can be reached from \"have\" commits.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n  Ralf Baechle <ralf@linux-mips.org> writes:\n\n    >> [PATCH] fetch-pack: give up after getting too many \"ack continue\"\n    >\n    > So I did test your patch.  In the big, slow repository it cuts down the\n    > time for a\n    >\n    >   git fetch git://www./.../linux-2.6.16.y.git master:v2.6.16-stable\n    >\n    > from like 6min to about 7s.\n    >\n    > Thanks!\n\n  This patch is still rough, but it passes my test of asking for\n  \"master\" from git.git repository into a repository that is a\n  merge between linux-2.6.git and a slightly older git.git.\n\n  Without this change, and without the client-side hack Ralf\n  tested, it ends up walking down the entire kernel history.\n\n  The code to walk back from wanted ref is unnecessarily ugly and\n  inefficient -- if we only support a handful want's (say 25) at a\n  time, we could make the traversal go as we receive \"have\" by\n  using something similar to what show-branches does.  I am\n  reworking on that part.\n\n upload-pack.c |  182 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 files changed, 167 insertions(+), 15 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 47560c9..e57733b 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -11,12 +11,18 @@ static const char upload_pack_usage[] = \n #define THEY_HAVE (1U << 0)\n #define OUR_REF (1U << 1)\n #define WANTED (1U << 2)\n+#define COMMON_KNOWN (1U << 3)\n+\n+#define TRACE_SEEN (1U << 4)\n+#define TRACE_BASE 5\n+#define MAX_TRACE 20 /* should not exceed bits_per_int - TRACE_BASE */\n+\n #define MAX_HAS 256\n #define MAX_NEEDS 256\n static int nr_has = 0, nr_needs = 0, multi_ack = 0, nr_our_refs = 0;\n static int use_thin_pack = 0;\n-static unsigned char has_sha1[MAX_HAS][20];\n-static unsigned char needs_sha1[MAX_NEEDS][20];\n+static struct object *has_sha1[MAX_HAS];\n+static struct object *needs_sha1[MAX_NEEDS];\n static unsigned int timeout = 0;\n \n static void reset_timeout(void)\n@@ -69,19 +75,22 @@ static void create_pack_file(void)\n \t\tif (create_full_pack || MAX_NEEDS <= nr_needs)\n \t\t\t*p++ = \"--all\";\n \t\telse {\n+\t\t\tstruct object **o = needs_sha1;\n \t\t\tfor (i = 0; i < nr_needs; i++) {\n \t\t\t\t*p++ = buf;\n-\t\t\t\tmemcpy(buf, sha1_to_hex(needs_sha1[i]), 41);\n+\t\t\t\tmemcpy(buf, sha1_to_hex((*o++)->sha1), 41);\n \t\t\t\tbuf += 41;\n \t\t\t}\n \t\t}\n-\t\tif (!create_full_pack)\n+\t\tif (!create_full_pack) {\n+\t\t\tstruct object **o = has_sha1;\n \t\t\tfor (i = 0; i < nr_has; i++) {\n \t\t\t\t*p++ = buf;\n \t\t\t\t*buf++ = '^';\n-\t\t\t\tmemcpy(buf, sha1_to_hex(has_sha1[i]), 41);\n+\t\t\t\tmemcpy(buf, sha1_to_hex((*o++)->sha1), 41);\n \t\t\t\tbuf += 41;\n \t\t\t}\n+\t\t}\n \t\t*p++ = NULL;\n \t\texecv_git_cmd(argv);\n \t\tdie(\"git-upload-pack: unable to exec git-rev-list\");\n@@ -93,6 +102,125 @@ static void create_pack_file(void)\n \tdie(\"git-upload-pack: unable to exec git-pack-objects\");\n }\n \n+static int trace_want(struct object **trace, int cnt)\n+{\n+\t/* start from these cnt objects, traverse the reachability\n+\t * chain, without parsing new objects, to see if we can\n+\t * reach objects they have.\n+\t */\n+\tint i, j;\n+\tunsigned trace_flags = 0;\n+\tstruct object_list *list = NULL;\n+\n+\tfor (i = 0; i < cnt; i++)\n+\t\ttrace_flags |= (1U << (TRACE_BASE + i));\n+\n+\tfor (i = 0; i < obj_allocs; i++)\n+\t\tif (objs[i])\n+\t\t\tobjs[i]->flags &= ~trace_flags;\n+\n+\tfor (i = 0; i < cnt; i++) {\n+\t\ttrace[i]->flags |= 1U << (TRACE_BASE + i);\n+\t\tobject_list_insert(trace[i], &list);\n+\t}\n+\n+\twhile (list) {\n+\t\tstruct object_list *next = list->next;\n+\t\tstruct object *o = list->item;\n+\t\tunsigned flags = o->flags & trace_flags;\n+\n+\t\tfree(list);\n+\t\tlist = next;\n+\t\tif (o->flags & TRACE_SEEN)\n+\t\t\tcontinue;\n+\t\to->flags |= TRACE_SEEN;\n+\t\tif (!strcmp(o->type, tag_type)) {\n+\t\t\to = deref_tag(o, NULL, 0);\n+\t\t\tif (o && (o->flags & trace_flags) != flags) {\n+\t\t\t\to->flags |= flags;\n+\t\t\t\tobject_list_insert(o, &list);\n+\t\t\t}\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(o->type, commit_type)) {\n+\t\t\tstruct commit *c = (struct commit *)o;\n+\t\t\tstruct commit_list *l = c->parents;\n+\t\t\twhile (l) {\n+\t\t\t\tstruct commit *p = l->item;\n+\t\t\t\tl = l->next;\n+\t\t\t\tif ((p->object.flags & trace_flags) != flags) {\n+\t\t\t\t\tp->object.flags |= flags;\n+\t\t\t\t\tobject_list_insert(&p->object, &list);\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* Now scan the objects they have, and see if the wanted one\n+\t * reach which ones.\n+\t */\n+\tfor (j = 0; j < nr_needs; j++) {\n+\t\tfor (i = 0;\n+\t\t     (i < nr_has &&\n+\t\t      !(needs_sha1[j]->flags & COMMON_KNOWN));\n+\t\t     i++) {\n+\t\t\tif (has_sha1[i]->flags & (1U << (TRACE_BASE + j)))\n+\t\t\t\tneeds_sha1[j]->flags |= COMMON_KNOWN;\n+\t\t}\n+\t}\n+\n+\tfor (j = 0; j < nr_needs; j++) {\n+\t\tif (!(needs_sha1[j]->flags & COMMON_KNOWN))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static void check_want_heads(void)\n+{\n+\t/* Do not keep saying \"ack continue\" if we already know\n+\t * common ancestor for all the \"want\"ed heads.  This is\n+\t * particularly important if some of the \"have\" heads does\n+\t * not share any root commit with us.  Otherwise we would\n+\t * keep asking for that branch, hoping we might get a better\n+\t * common ancestor than we already have.\n+\t */\n+\tint i, still_missing;\n+\tstruct object *trace[MAX_TRACE];\n+\tint trace_bit;\n+\n+\tif (!multi_ack)\n+\t\treturn;\n+\n+\tstill_missing = 0;\n+\ttrace_bit = 0;\n+\tfor (i = 0; still_missing && i < nr_needs; i++) {\n+\t\tstruct object *o = needs_sha1[i];\n+\t\tif (o->flags & COMMON_KNOWN)\n+\t\t\tcontinue;\n+\t\tif (strcmp(o->type, tag_type) &&\n+\t\t    strcmp(o->type, commit_type))\n+\t\t\t/* Asking for non traceable types - there\n+\t\t\t * is not much we can do to optimize it here.\n+\t\t\t * We will let rev-list deal with it.\n+\t\t\t */\n+\t\t\tcontinue;\n+\t\tif (trace_bit < MAX_TRACE) {\n+\t\t\ttrace[trace_bit] = o;\n+\t\t\ttrace_bit++;\n+\t\t}\n+\t\telse {\n+\t\t\tstill_missing = trace_want(trace, trace_bit);\n+\t\t\ttrace_bit = 0;\n+\t\t}\n+\t}\n+\tif (trace_bit && !still_missing)\n+\t\tstill_missing = trace_want(trace, trace_bit);\n+\n+\tif (!still_missing)\n+\t\tmulti_ack = 0;\n+}\n+\n static int got_sha1(char *hex, unsigned char *sha1)\n {\n \tif (get_sha1_hex(hex, sha1))\n@@ -107,15 +235,39 @@ static int got_sha1(char *hex, unsigned \n \t\t\tdie(\"oops (%s)\", sha1_to_hex(sha1));\n \t\tif (o->type == commit_type) {\n \t\t\tstruct commit_list *parents;\n+\t\t\tint we_knew_they_have = 0;\n+\n+\t\t\t/* Because we deliberately stay behind by one\n+\t\t\t * window in order to make the protocol\n+\t\t\t * stream, many commits can already be in\n+\t\t\t * flight when we notice that the latest one\n+\t\t\t * in the series is already what we have.  Do\n+\t\t\t * not waste the has_sha1[] slot for extra commits\n+\t\t\t * sent that way.\n+\t\t\t *\n+\t\t\t * This relies on fetch-pack sending the \"have\"\n+\t\t\t * lines without skipping.\n+\t\t\t */\n \t\t\tif (o->flags & THEY_HAVE)\n-\t\t\t\treturn 0;\n-\t\t\to->flags |= THEY_HAVE;\n+\t\t\t\twe_knew_they_have = 1;\n+\t\t\telse\n+\t\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\tif (we_knew_they_have)\n+\t\t\t\treturn 0;\n \t\t}\n-\t\tmemcpy(has_sha1[nr_has++], sha1, 20);\n+\t\thas_sha1[nr_has++] = o;\n+\n+\t\t/* Check to see if we know a common ancestor for\n+\t\t * all the \"want\" heads, and if so turn multi_ack\n+\t\t * off.  There is nothing more gained by further\n+\t\t * exchange.\n+\t\t */\n+\t\tcheck_want_heads();\n+\n \t}\n \treturn 1;\n }\n@@ -141,7 +293,7 @@ static int get_common_commits(void)\n \t\tlen = strip(line, len);\n \t\tif (!strncmp(line, \"have \", 5)) {\n \t\t\tif (got_sha1(line+5, sha1) &&\n-\t\t\t\t\t(multi_ack || nr_has == 1)) {\n+\t\t\t    (multi_ack || nr_has == 1)) {\n \t\t\t\tif (nr_has >= MAX_HAS)\n \t\t\t\t\tmulti_ack = 0;\n \t\t\t\tpacket_write(1, \"ACK %s%s\\n\",\n@@ -156,7 +308,7 @@ static int get_common_commits(void)\n \t\t\tif (nr_has > 0) {\n \t\t\t\tif (multi_ack)\n \t\t\t\t\tpacket_write(1, \"ACK %s\\n\",\n-\t\t\t\t\t\t\tsha1_to_hex(last_sha1));\n+\t\t\t\t\t\t     sha1_to_hex(last_sha1));\n \t\t\t\treturn 0;\n \t\t\t}\n \t\t\tpacket_write(1, \"NAK\\n\");\n@@ -174,23 +326,21 @@ static int receive_needs(void)\n \tneeds = 0;\n \tfor (;;) {\n \t\tstruct object *o;\n-\t\tunsigned char dummy[20], *sha1_buf;\n+\t\tunsigned char sha1_buf[20];\n \t\tlen = packet_read_line(0, line, sizeof(line));\n \t\treset_timeout();\n \t\tif (!len)\n \t\t\treturn needs;\n \n-\t\tsha1_buf = dummy;\n \t\tif (needs == MAX_NEEDS) {\n \t\t\tfprintf(stderr,\n \t\t\t\t\"warning: supporting only a max of %d requests. \"\n \t\t\t\t\"sending everything instead.\\n\",\n \t\t\t\tMAX_NEEDS);\n \t\t}\n-\t\telse if (needs < MAX_NEEDS)\n-\t\t\tsha1_buf = needs_sha1[needs];\n \n-\t\tif (strncmp(\"want \", line, 5) || get_sha1_hex(line+5, sha1_buf))\n+\t\tif (strncmp(\"want \", line, 5) ||\n+\t\t    get_sha1_hex(line+5, sha1_buf))\n \t\t\tdie(\"git-upload-pack: protocol error, \"\n \t\t\t    \"expected to get sha, not '%s'\", line);\n \t\tif (strstr(line+45, \"multi_ack\"))\n@@ -211,6 +361,8 @@ static int receive_needs(void)\n \t\t\tdie(\"git-upload-pack: not our ref %s\", line+5);\n \t\tif (!(o->flags & WANTED)) {\n \t\t\to->flags |= WANTED;\n+\t\t\tif (needs < MAX_NEEDS)\n+\t\t\t\tneeds_sha1[needs] = o;\n \t\t\tneeds++;\n \t\t}\n \t}\n-- \n1.3.3.g2a0a\n"},{"id":"24177","messageId":"7v4px4osjv.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"20060525131241.GA8443@linux-mips.org","subject":"Re: Slow fetches of tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-26T23:27:48Z","receivedAt":"2006-07-26T23:27:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ralf Baechle <ralf@linux-mips.org> writes:\n\n> On Wed, May 24, 2006 at 04:43:02PM -0700, Linus Torvalds wrote:\n>\n>> Actually, maybe the problem is that Ralf's tree has two roots, because of \n>> the old CVS history. It might be following the other root down for the \n>> \"have\" part, since that one doesn't exist at all in the target and the \n>> other side will never acknowledge any of it. \n>> \n>> I'll play with it.\n>\n> Interesting idea, so I went to play with it, too.  I took a copy of the\n> tree and deleted all branches except the v2.6.16-stable tracking branch\n> which I pruned back to v2.6.16.17, then added a new branch starting at\n> the oldest commit, your initial import of the kernel tree:\n\nI've been looking at this issue again...\n\n> $ git branch junk 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n> $ git checkout junk\n> $ seq -f \"%05.0f\" 1 100 | while read i; do echo $i; echo $i > Makefile;\\\n>   git commit -s -m \"Blah $i\" Makefile; done\n>\n> So with this I get:\n>\n> $ git branch\n> * junk\n>   v2.6.16-stable\n> $\n>\n> If I now run\n>\n> $ strace git-fetch-pack --thin git://www.kernel.org/pub/scm/linux/kernel/\\\n> \tgit/stable/linux-2.6.16.y.git \\\n> \trefs/heads/master refs/tags/v2.6.16.18 2>&1 | grep have /tmp/xxx\n>\n> I get:\n\n... 100 newest commits from the junk branch and then all the\n    tags the downloader has are sent as \"have\"s.\n\nNow, sending the newest commits before sending the tags is\nunavoidable, since the other end does not know where you forked\nat (the purpose of the handshake is to find out where to begin\nwith).  But as soon as you send v2.6.16.17 (the latest tag that\nyou have in common with the other side, _and_ is a proper\nancestor of what you want -- v2.6.16.18 but that fact you do not\nknow yet), the server end should be able to say \"ok, we know\nenough\".  That is not happening.\n\nA few hints for debugging this:\n\n * local test is easier -- fetch-pack spawns upload-pack using\n   PATH and GIT_EXEC_PATH so set them to point at the updated\n   upload-pack being tested.\n\n * Passing the standard error from \"fetch-pack -v\" to \"name-rev\n   --stdin\" makes it a bit more pleasant to see what is going on.\n\nWith the attached patch, the server side tells the client to\nstop immediately after it says it has the commit tagged as\nv2.6.16.17 while asking for v2.6.16.18.  With your \"100 commits\non junk\" repository, it does not make much of a difference,\nthough.  The reasons are (1) the 100 commits on \"junk\" are much\nyounger than any of the tags, so they are sent anyway, (2) we\nhave a 32-commit window, and keep one window in flight to make\nthe protocol stream, which means there will be max 64 \"have\"\nthat are in flight unacked, and a clone of linux-2.6.16.y\nrepository that has up to v2.6.16.17 tag has only 52 tags.\n\nSo we end up sending all the tags anyway in this particular\ncase.\n\nI've thought about sending tags and only _tips_ of branches\nfirst, but I think that would have a grave performance impact on\nmore normal cases.  If you are dealing with a remote repository\nwith a bunch of tags, your \"master\" is ahead of the remote\nrepository, and you do not use tracking branch to track the\nremote (pretend you are Linus and pulling from a subsystem\nmaintainer), then you obviously do not want to send v2.6.12-rc2\ntag before you send commits from your \"master\" branch to get to\nwhere your subsystem maintainer forked from you (otherwise the\nremote side would say \"I do not know your 'master' commit, but\nnow we know we have this ancient v2.6.12-rc2 in common, so let's\nhave a pack between that and the tip of the subsystem tree\"), so\nI do think sending \"100 commits on junk branch\" is unavoidable.\n\nI think the attached patch is safe in general, but somebody may\nwant to give an extra set of eyeballs to double check the logic\nis sane.\n\n-- >8 --\nupload-pack: squelch downloader more aggressively under multi-ack\n\nWhen the server side sees \"have\" line that makes all the \"want\"\ncommits somehow reachable from one of the \"have\" lines so far,\nstop responding \"continue\" to prevent the other end going down\nto send too many refs.\n\n---\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 617ee46..ac42d0d 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -452,8 +452,13 @@ static int get_common_commits(void)\n \t\t\tdefault:\n \t\t\t\tmemcpy(hex, sha1_to_hex(sha1), 41);\n \t\t\t\tif (multi_ack) {\n-\t\t\t\t\tconst char *msg = \"ACK %s continue\\n\";\n-\t\t\t\t\tpacket_write(1, msg, hex);\n+\t\t\t\t\tconst char *msg = \"ACK %s%s\\n\";\n+\t\t\t\t\tconst char *cont = \" continue\";\n+\t\t\t\t\tif (ok_to_give_up()) {\n+\t\t\t\t\t\tcont = \"\";\n+\t\t\t\t\t\tmulti_ack = 0;\n+\t\t\t\t\t}\n+\t\t\t\t\tpacket_write(1, msg, hex, cont);\n \t\t\t\t\tmemcpy(last_hex, hex, 41);\n \t\t\t\t}\n \t\t\t\telse if (have_obj.nr == 1)\n"},{"id":"24297","messageId":"Pine.LNX.4.63.0607281233120.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4277","inReplyTo":"7v4px4osjv.fsf@assigned-by-dhcp.cox.net","subject":"Re: Slow fetches of tags","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-28T10:42:22Z","receivedAt":"2006-07-28T10:42:22Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 26 Jul 2006, Junio C Hamano wrote:\n\n> I think the attached patch is safe in general, but somebody may\n> want to give an extra set of eyeballs to double check the logic\n> is sane.\n\nThe only gripe I have with it is that reachable() is relatively expensive, \nand it might be misused by a nasty client, making the server go down the \nwhole history. I have no idea, though, how to prevent that.\n\nCiao,\nDscho\n"},{"id":"24298","messageId":"Pine.LNX.4.63.0607281308280.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4277","inReplyTo":"7v4px4osjv.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] Teach the git wrapper about --name-rev and --name-rev-by-tags","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-28T11:12:08Z","receivedAt":"2006-07-28T11:12:08Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nNow you can say\n\n\tgit --name-rev log\n\ninstead of\n\n\tgit log | git name-rev --stdin | less\n\nwith the benefit that diff.color=auto still works.\n\nThere is also a shortcut \"-n\" for --name-rev. The option \n--name-rev-by-tags (or -t) tries to name the revs by tags instead of all \nrefs, which is nicer when talking to other people, since their heads may \nbe different from yours (I feel like talking to Zaphod ;-).\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n\n---\n\n\tOn Wed, 26 Jul 2006, Junio C Hamano wrote:\n\n\t>  * Passing the standard error from \"fetch-pack -v\" to \"name-rev\n\t>    --stdin\" makes it a bit more pleasant to see what is going on.\n\n\tThis patch makes it even easier.\n\n Documentation/git.txt |   12 ++++++++++--\n cache.h               |    1 +\n git.c                 |    9 +++++++--\n pager.c               |   41 +++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 59 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/git.txt b/Documentation/git.txt\nindex 7310a2b..eae930f 100644\n--- a/Documentation/git.txt\n+++ b/Documentation/git.txt\n@@ -9,7 +9,8 @@ git - the stupid content tracker\n SYNOPSIS\n --------\n 'git' [--version] [--exec-path[=GIT_EXEC_PATH]] [-p|--paginate]\n-\t[--bare] [--git-dir=GIT_DIR] [--help] COMMAND [ARGS]\n+\t[-n|--name-rev] [-t|--name-rev-by-tags] [--bare]\n+\t[--git-dir=GIT_DIR] [--help] COMMAND [ARGS]\n \n DESCRIPTION\n -----------\n@@ -45,12 +46,19 @@ OPTIONS\n -p|--paginate::\n \tPipe all output into 'less' (or if set, $PAGER).\n \n+-n|--name-rev:\n+\tTry naming all SHA1s, and page the result (see\n+\tlink:git-name-rev[1] for a detailed explanation).\n+\n+-t|--name-rev-by-tags:\n+\tSame as '--name-rev', but try to name the SHA1s by tags.\n+\n --git-dir=<path>::\n \tSet the path to the repository. This can also be controlled by\n \tsetting the GIT_DIR environment variable.\n \n --bare::\n-\tSame as --git-dir=`pwd`.\n+\tSame as  '--git-dir=`pwd`'.\n \n FURTHER DOCUMENTATION\n ---------------------\ndiff --git a/cache.h b/cache.h\nindex 8891073..d6c5edb 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -391,6 +391,7 @@ extern int receive_keep_pack(int fd[2], \n \n /* pager.c */\n extern void setup_pager(void);\n+extern void setup_name_rev_pager(int by_tags);\n extern int pager_in_use;\n \n /* base85 */\ndiff --git a/git.c b/git.c\nindex 4ea5efb..4206b43 100644\n--- a/git.c\n+++ b/git.c\n@@ -63,9 +63,14 @@ static int handle_options(const char*** \n \t\t\t\tputs(git_exec_path());\n \t\t\t\texit(0);\n \t\t\t}\n-\t\t} else if (!strcmp(cmd, \"-p\") || !strcmp(cmd, \"--paginate\")) {\n+\t\t} else if (!strcmp(cmd, \"-p\") || !strcmp(cmd, \"--paginate\"))\n \t\t\tsetup_pager();\n-\t\t} else if (!strcmp(cmd, \"--git-dir\")) {\n+\t\telse if (!strcmp(cmd, \"-n\") || !strcmp(cmd, \"--name-rev\"))\n+\t\t\tsetup_name_rev_pager(0);\n+\t\telse if (!strcmp(cmd, \"-t\") ||\n+\t\t\t\t!strcmp(cmd, \"--name-rev-by-tags\"))\n+\t\t\tsetup_name_rev_pager(1);\n+\t\telse if (!strcmp(cmd, \"--git-dir\")) {\n \t\t\tif (*argc < 1)\n \t\t\t\treturn -1;\n \t\t\tsetenv(\"GIT_DIR\", (*argv)[1], 1);\ndiff --git a/pager.c b/pager.c\nindex 280f57f..48b2467 100644\n--- a/pager.c\n+++ b/pager.c\n@@ -53,3 +53,44 @@ void setup_pager(void)\n \tdie(\"unable to execute pager '%s'\", pager);\n \texit(255);\n }\n+\n+void setup_name_rev_pager(int by_tags)\n+{\n+\tpid_t pid;\n+\tint fd[2];\n+\n+\tif (!isatty(1))\n+\t\treturn;\n+\n+\tpager_in_use = 1; /* means we are emitting to terminal */\n+\n+\tif (pipe(fd) < 0)\n+\t\treturn;\n+\tpid = fork();\n+\tif (pid < 0) {\n+\t\tclose(fd[0]);\n+\t\tclose(fd[1]);\n+\t\treturn;\n+\t}\n+\n+\t/* return in the child */\n+\tif (!pid) {\n+\t\tdup2(fd[1], 1);\n+\t\tclose(fd[0]);\n+\t\tclose(fd[1]);\n+\t\treturn;\n+\t}\n+\n+\t/* The original process turns into paging name-rev */\n+\tdup2(fd[0], 0);\n+\tclose(fd[0]);\n+\tclose(fd[1]);\n+\n+\tsetup_pager();\n+\tif (by_tags)\n+\t\texecl(\"git\", \"git\", \"name-rev\", \"--tags\", \"--stdin\", NULL);\n+\telse\n+\t\texecl(\"git\", \"git\", \"name-rev\", \"--stdin\", NULL);\n+\tdie(\"unable to execute git-name-rev\");\n+\texit(255);\n+}\n-- \n1.4.2.rc2.g61d8\n"},{"id":"24307","messageId":"7vy7udloq1.fsf@assigned-by-dhcp.cox.net","threadId":"4277","inReplyTo":"Pine.LNX.4.63.0607281308280.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Teach the git wrapper about --name-rev and --name-rev-by-tags","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-07-28T15:43:18Z","receivedAt":"2006-07-28T15:43:18Z","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> \tOn Wed, 26 Jul 2006, Junio C Hamano wrote:\n>\n> \t>  * Passing the standard error from \"fetch-pack -v\" to \"name-rev\n> \t>    --stdin\" makes it a bit more pleasant to see what is going on.\n>\n> \tThis patch makes it even easier.\n\nProbably wouldn't for that particular one, since what I wanted\nto do was \"git fetch-pack -v 2>&1 | git name-rev >/var/tmp/1\",\nso isatty(1) check in setup_name_rev_pager() is defeated by\nredirection, and the information I wanted to pass name-rev would\nnot have passed it anyway.\n\nBut this _might_ be useful for other more general cases.  I'm\nnot sure -- it feels somewhat like a hack, though.\n"},{"id":"24311","messageId":"Pine.LNX.4.64.0607280952200.4168@g5.osdl.org","threadId":"4277","inReplyTo":"Pine.LNX.4.63.0607281308280.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Teach the git wrapper about --name-rev and --name-rev-by-tags","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-07-28T16:59:11Z","receivedAt":"2006-07-28T16:59:11Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 28 Jul 2006, Johannes Schindelin wrote:\n> \n> Now you can say\n> \n> \tgit --name-rev log\n\nI think this is wrong.\n\nIt may be a straightforward translation of\n\n> \tgit log | git name-rev --stdin | less\n\nbut that doesn't make it any more \"correct\".\n\n>From a logical standpoint, it should be an argument to the _logging_, not \nto the main git binary, so it should be\n\n\tgit log --name-rev\n\nand you should do the parsing (and the output) inside revision.c.\n\nAlso, I doubt most people want every release named. I think the common \ncase would be that you want those releases named that match heads (and \ntags in particular) _exactly_. If you want everything named, maybe you \nwant to do \"--name-rev-all\" or something.\n\nHmm?\n\n(That would also likely perform a lot better)\n\n\t\tLinus\n"},{"id":"24314","messageId":"Pine.LNX.4.63.0607282042470.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4277","inReplyTo":"Pine.LNX.4.64.0607280952200.4168@g5.osdl.org","subject":"Re: [PATCH] Teach the git wrapper about --name-rev and --name-rev-by-tags","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-28T18:53:58Z","receivedAt":"2006-07-28T18:53:58Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 28 Jul 2006, Linus Torvalds wrote:\n\n> On Fri, 28 Jul 2006, Johannes Schindelin wrote:\n> > \n> > Now you can say\n> > \n> > \tgit --name-rev log\n> \n> I think this is wrong.\n\nI think it is not wrong. :-)\n\n> It may be a straightforward translation of\n> \n> > \tgit log | git name-rev --stdin | less\n> \n> but that doesn't make it any more \"correct\".\n\nI use it also for other git commands, so this was very much on purpose.\n\n> Also, I doubt most people want every release named.\n\nYou are probably right. But _I_ want to know that e.g. commit \na025463bc0ec2c894a88f2dfb44cf88ba71bb712 is really tags/v1.4.0^0~27^2. \nBoth are immutable, but the latter is nicer to people than to computers.\n\n> I think the common case would be that you want those releases named that \n> match heads (and tags in particular) _exactly_. If you want everything \n> named, maybe you want to do \"--name-rev-all\" or something.\n> \n> Hmm?\n> \n> (That would also likely perform a lot better)\n\nTrue. But then, you probably know which head it is, because you probably \nspecified it yourself on the command line.\n\nCiao,\nDscho\n"},{"id":"24339","messageId":"fcaeb9bf0607290543h12b70c74q54a1fbfc3c8e3b7e@mail.gmail.com","threadId":"4277","inReplyTo":"Pine.LNX.4.63.0607282042470.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Teach the git wrapper about --name-rev and --name-rev-by-tags","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2006-07-29T12:43:29Z","receivedAt":"2006-07-29T12:43:29Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On 7/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> You are probably right. But _I_ want to know that e.g. commit\n> a025463bc0ec2c894a88f2dfb44cf88ba71bb712 is really tags/v1.4.0^0~27^2.\n> Both are immutable, but the latter is nicer to people than to computers.\nI think so too. I had requested a similar feature on the git survey\nand was surprised to see this patch. I'd appreciate it.\n"},{"id":"24340","messageId":"Pine.LNX.4.63.0607291446400.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4277","inReplyTo":"fcaeb9bf0607290543h12b70c74q54a1fbfc3c8e3b7e@mail.gmail.com","subject":"Re: [PATCH] Teach the git wrapper about --name-rev and --name-rev-by-tags","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-07-29T12:47:03Z","receivedAt":"2006-07-29T12:47:03Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 29 Jul 2006, Nguyn Thái Ngc Duy wrote:\n\n> On 7/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> > You are probably right. But _I_ want to know that e.g. commit\n> > a025463bc0ec2c894a88f2dfb44cf88ba71bb712 is really tags/v1.4.0^0~27^2.\n> > Both are immutable, but the latter is nicer to people than to computers.\n> I think so too. I had requested a similar feature on the git survey\n> and was surprised to see this patch. I'd appreciate it.\n\nNow, guess three times where the idea comes from. ;-)\n\nCiao,\nDscho\n"}]}