# [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack 6 messages from 2005-10-25 to 2005-10-25. Participants: Johannes Schindelin, Junio C Hamano. Thread: https://gitlist.dev/t/2213 ## Johannes Schindelin, 2005-10-25 06:59 Subject: [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0510250854240.22398%40wbgn013.biozentrum.uni-wuerzburg.de ``` Sort the refs by date again (but only the refs). This helps when the server does not support multi_ack, since the more likely candidates for common revs are the younger ones. Also, it helps avoid traffic, as younger revs can have older revs as ancestors, but not vice versa. Therefore, when the server ack's a younger rev, chances are that the older rev never gets sent. Signed-off-by: Johannes Schindelin --- Yesterday, I pulled from the git repository, and it wanted to give me 961 objects! When analyzing this, I found out that my version of git-fetch-pack sent the oldest refs first. The newest was never sent, because the oldest was ack'ed right away. fetch-pack.c | 35 +++++++++++++++++++++++------------ 1 files changed, 23 insertions(+), 12 deletions(-) diff --git a/fetch-pack.c b/fetch-pack.c index 57602b9..3efa652 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -22,30 +22,41 @@ static struct commit_list *rev_list = NU static struct commit_list *rev_list_end = NULL; static unsigned long non_common_revs = 0; -static void rev_list_append(struct commit *commit, int mark) +static void rev_list_push(struct commit *commit, int mark, + int insert) { if (!(commit->object.flags & mark)) { commit->object.flags |= mark; - if (rev_list == NULL) { + if (insert) + insert_by_date(commit, &rev_list); + else commit_list_insert(commit, &rev_list); + + if (!rev_list_end) rev_list_end = rev_list; - } else { - commit_list_insert(commit, &(rev_list_end->next)); + else if (rev_list_end->next) rev_list_end = rev_list_end->next; - } if (!(commit->object.flags & COMMON)) non_common_revs++; } } -static int rev_list_append_sha1(const char *path, const unsigned char *sha1) +/* + The refs are not just appended to the rev_list, but rather inserted + by date. It is just more efficient that way, since the edges of the + common commits are more likely to be recent than not. + Also, it makes fetch-pack plays nice with servers which do not + understand the multi_ack extension. +*/ + +static int rev_list_insert_ref(const char *path, const unsigned char *sha1) { struct object *o = deref_tag(parse_object(sha1)); if (o->type == commit_type) - rev_list_append((struct commit *)o, SEEN); + rev_list_push((struct commit *)o, SEEN, 1); return 0; } @@ -56,7 +67,7 @@ static void mark_common(struct commit *c struct object *o = (struct object *)commit; o->flags |= COMMON; if (!(o->flags & SEEN)) - rev_list_append(commit, SEEN); + rev_list_push(commit, SEEN, 0); else { struct commit_list *parents; @@ -111,7 +122,7 @@ static const unsigned char* get_rev() if (mark & COMMON) mark_common(parents->item); else - rev_list_append(parents->item, mark); + rev_list_push(parents->item, mark, 0); parents = parents->next; } @@ -128,7 +139,7 @@ static int find_common(int fd[2], unsign int count = 0, flushes = 0, multi_ack = 0, retval; const unsigned char *sha1; - for_each_ref(rev_list_append_sha1); + for_each_ref(rev_list_insert_ref); fetching = 0; for ( ; refs ; refs = refs->next) { @@ -150,8 +161,8 @@ static int find_common(int fd[2], unsign o = deref_tag(o); if (o->type == commit_type) - rev_list_append((struct commit *)o, - COMMON_REF | SEEN); + rev_list_push((struct commit *)o, + COMMON_REF | SEEN, 1); continue; } ``` ## Junio C Hamano, 2005-10-25 08:30 Subject: Re: [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack Message-ID: <7vy84igfrl.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vy84igfrl.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Johannes Schindelin writes: > + if (insert) > + insert_by_date(commit, &rev_list); > + else > commit_list_insert(commit, &rev_list); Hmph. I do not think insert_by_date and commit_list_insert on the same commit_list would play well together, since the former assumes that the list is already sorted by age (i.e. younger ones near the head, older ones close to the tail). But you are right. If you made 20 commits on top of my "master" branch head, we should send those 20 (and the commit you based on your changes, which the other end has), way before sending the ancient v0.99 tag. Probably, we should never be sending v0.99 tag as "have" if we are going to send your "master" branch head, since the commit that tag refers to is reachable by your "master" branch head but there are a lot more commit between them, some of which will give us better "common" selected, and that v0.99 tag is what the other end said they have so is known to be ACKed if sent. Although we are doing a traversal on the fetch side to figure out the commit ancestry chain, I think we are not fully utilizing the information we receive from the other end. Typically we pull specific heads only, so get_remote_heads() culls the information about remote refs and you would not have a chance to know that v0.99 tag you have in your .git/refs/tags is something the remote also has, unless you asked for that particular tag. I wonder if we can take advantage of that information without discarding it. For example, get_remote_heads() itself knows the object name of v0.99.8 tag and the object name of the commit the tag refers to, and you have those objects locally already. If you have many local branches, and v0.99.8 commit is reachable from the heads of all of your local branches, then you should be able to tell that you do not have to (and you do not want to) send "have" for v0.99.7 and older tags even though they are also in your .git/refs/, since you know they are all reachable from v0.99.8 commit and likely to be worse common than v0.99.8. The best common is somewhere between v0.99.8 and the tips of your local branches. This is a minor nit but I think you no longer need to have the rev_list_end in this version. It is only used to maintain itself and not for any other purpose as far as I can see. ``` ## Johannes Schindelin, 2005-10-25 09:51 Subject: Re: [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0510251104470.24174%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <7vy84igfrl.fsf@assigned-by-dhcp.cox.net> ``` Hi, On Tue, 25 Oct 2005, Junio C Hamano wrote: > Johannes Schindelin writes: > > > + if (insert) > > + insert_by_date(commit, &rev_list); > > + else > > commit_list_insert(commit, &rev_list); > > Hmph. I do not think insert_by_date and commit_list_insert on > the same commit_list would play well together, since the former > assumes that the list is already sorted by age (i.e. younger ones > near the head, older ones close to the tail). I´m sorry. The 2nd time, it should be &(rev_list_end->next), not &rev_list. (See my reply to myself). In effect, rev_list would be filled first by insert_by_date() with the refs we have and the known-to-be-common refs from the other side. From then on, only commit_list_insert would effectively *append* the ancestors. So it does play nicely. If there´s not yet another bug. > But you are right. If you made 20 commits on top of my "master" > branch head, we should send those 20 (and the commit you based > on your changes, which the other end has), way before sending > the ancient v0.99 tag. Probably, we should never be sending > v0.99 tag as "have" if we are going to send your "master" branch > head, since the commit that tag refers to is reachable by your > "master" branch head but there are a lot more commit between > them, some of which will give us better "common" selected, and > that v0.99 tag is what the other end said they have so is known > to be ACKed if sent. You´re right. Complete common refs are sent even if they are ancestors of other complete common refs. I´ll think about that. > Although we are doing a traversal on the fetch side to figure > out the commit ancestry chain, I think we are not fully > utilizing the information we receive from the other end. > Typically we pull specific heads only, so get_remote_heads() > culls the information about remote refs and you would not have a > chance to know that v0.99 tag you have in your .git/refs/tags is > something the remote also has, unless you asked for that > particular tag. I wonder if we can take advantage of that > information without discarding it. For example, > get_remote_heads() itself knows the object name of v0.99.8 tag > and the object name of the commit the tag refers to, and you > have those objects locally already. If you have many local > branches, and v0.99.8 commit is reachable from the heads of all > of your local branches, then you should be able to tell that you > do not have to (and you do not want to) send "have" for v0.99.7 > and older tags even though they are also in your .git/refs/, > since you know they are all reachable from v0.99.8 commit and > likely to be worse common than v0.99.8. The best common is > somewhere between v0.99.8 and the tips of your local branches. IOW v0.99.7 is an ancestor of v0.99.8, which is complete. Therefore, the former should not be sent. Remember that we do not have to send the optimal edges: If v0.99.7 were the optimal common rev for some_branch, but we send v0.99.8, the server side will do a "git-rev-list some_branch ^v0.99.8", which has the same effect as if passing "^v0.99.7" instead. So let´s change the definition of COMMON_REF to not include COMMON. Then, do not mark the COMMON_REFs in find_common, but before that. And mark their ancestors (as far as they were already parsed in everything_local()) as COMMON. Oh, and pass nr_match=0 to get_remote_heads() and do the culling after using the information. > This is a minor nit but I think you no longer need to have the > rev_list_end in this version. It is only used to maintain > itself and not for any other purpose as far as I can see. My mistake: the revs should be appended, not unshifted into rev_list. If they got unshifted, that would mean that we first send all the ancestors of the youngest refs until we get a common rev, then all the ancestors of the 2nd youngest, etc. When the revs are appended instead, first all the refs get sent (sorted by date), then the parents of them (sorted by the date of the refs), then their grand parents, etc. While writing this, I cannot remember why I decided not to insert_by_date() all the time. Ciao, Dscho ``` ## Junio C Hamano, 2005-10-25 18:56 Subject: Re: [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack Message-ID: <7vll0he88u.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vll0he88u.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Johannes Schindelin writes: >> But you are right. If you made 20 commits on top of my "master" >> branch head, we should send those 20 (and the commit you based >> on your changes, which the other end has), way before sending >> the ancient v0.99 tag. Probably, we should never be sending >> v0.99 tag as "have" if we are going to send your "master" branch >> head, since the commit that tag refers to is reachable by your >> "master" branch head but there are a lot more commit between >> them, some of which will give us better "common" selected, and >> that v0.99 tag is what the other end said they have so is known >> to be ACKed if sent. > > You´re right. Complete common refs are sent even if they are ancestors of > other complete common refs. I´ll think about that. I just realized that I have two refs you would rather send the last while fetching from me most of the time: junio-gpg-pub tag and todo head. If you manage to get acked either by non multi aware remote before saying "have" on anything on the main branch, I think you would get *everything* back --- which is quite bad. ``` ## Junio C Hamano, 2005-10-25 23:32 Subject: Re: [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack Message-ID: <7vll0hcgv3.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vll0hcgv3.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Johannes Schindelin writes: > On Tue, 25 Oct 2005, Junio C Hamano wrote: > >> But you are right. If you made 20 commits on top of my "master" >> branch head, we should send those 20 (and the commit you based >> on your changes, which the other end has), way before sending >> the ancient v0.99 tag. Probably, we should never be sending >> v0.99 tag as "have" if we are going to send your "master" branch >> head, since the commit that tag refers to is reachable by your >> "master" branch head but there are a lot more commit between >> them, some of which will give us better "common" selected, and >> that v0.99 tag is what the other end said they have so is known >> to be ACKed if sent. > > You´re right. Complete common refs are sent even if they are ancestors of > other complete common refs. I´ll think about that. I think you should be able to do something similar to what git-show-branch --independent does, except that the current show-branch implementation sucks. It wastes one-bit per ref head, which is not too bad if we deal only with branches (who would sanely keep more than 29 branches in a repo except Jeff ;-) but is useless for a repository with any reasonable history and a lot of tags. ``` ## Johannes Schindelin, 2005-10-25 23:53 Subject: Re: [PATCH] Make fetch-pack play nicer with servers which do not speak multi_ack Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0510260150400.31269%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <7vll0hcgv3.fsf@assigned-by-dhcp.cox.net> ``` Hi, On Tue, 25 Oct 2005, Junio C Hamano wrote: > Johannes Schindelin writes: > > > You're right. Complete common refs are sent even if they are ancestors > > of other complete common refs. I'll think about that. > > I think you should be able to do something similar to what > git-show-branch --independent does, except that the current > show-branch implementation sucks. I have a patch simmering, but I hesitate to send it out, lest you go and put it into master before I found the obvious bugs ;-) > It wastes one-bit per ref head, which is not too bad if we deal only > with branches (who would sanely keep more than 29 branches in a repo > except Jeff ;-) [...] Well, I do! I *love* topic branches. Sometimes I even interrupt my regular work to create a random one ;-) ```