{"thread":{"id":"1802","subject":"[PATCH] Fix fetch completeness assumptions","startedAt":"2005-09-15T01:31:42Z","lastAt":"2005-09-18T17:38:39Z","messageCount":11,"participants":["Daniel Barkalow","Junio C Hamano","Sergey Vlasov"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"8572","messageId":"Pine.LNX.4.63.0509142120020.23242@iabervon.org","threadId":"1802","inReplyTo":null,"subject":"[PATCH] Fix fetch completeness assumptions","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-15T01:31:42Z","receivedAt":"2005-09-15T01:31:42Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Don't assume that any commit we have is complete; assume that any ref\nwe have is complete.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n\n---\nOnly lightly tested, but it seems to work. Marks all of the commits in \nrefs, and their ancestors back as far as the date of the commit it's \nprocessing. If the commit it's processing is marked, it doesn't recurse \ninto it.\n\nThis should make it very difficult to get it to produce a situation where \nit completes without giving you complete information, and it shouldn't \nprocess commits that are accessible from refs.\n\n fetch.c |   28 ++++++++++++++++++++++++++--\n 1 files changed, 26 insertions(+), 2 deletions(-)\n\n39216139abc4f2759f7b55d11fa2f7e7c155898c\ndiff --git a/fetch.c b/fetch.c\n--- a/fetch.c\n+++ b/fetch.c\n@@ -62,11 +62,21 @@ static int process_tree(struct tree *tre\n \treturn 0;\n }\n \n+struct commit_list *complete = NULL;\n+\n static int process_commit(struct commit *commit)\n {\n \tif (parse_commit(commit))\n \t\treturn -1;\n \n+\twhile (complete && complete->item->date >= commit->date) {\n+\t\tpop_most_recent_commit(&complete, 1);\n+\t}\n+\t\t\n+\n+\tif (commit->object.flags & 1)\n+\t\treturn 0;\n+\n \tmemcpy(current_commit_sha1, commit->object.sha1, 20);\n \n \tif (get_tree) {\n@@ -78,8 +88,6 @@ static int process_commit(struct commit \n \tif (get_history) {\n \t\tstruct commit_list *parents = commit->parents;\n \t\tfor (; parents; parents = parents->next) {\n-\t\t\tif (has_sha1_file(parents->item->object.sha1))\n-\t\t\t\tcontinue;\n \t\t\tif (process(parents->item->object.sha1,\n \t\t\t\t    commit_type))\n \t\t\t\treturn -1;\n@@ -126,6 +134,7 @@ static int process_object(struct object \n static int process(unsigned char *sha1, const char *type)\n {\n \tstruct object *obj = lookup_object_type(sha1, type);\n+\n \tif (has_sha1_file(sha1)) {\n \t\tparse_object(sha1);\n \t\t/* We already have it, so we should scan it now. */\n@@ -179,6 +188,19 @@ static int interpret_target(char *target\n \treturn -1;\n }\n \n+static int mark_complete(const char *path, const unsigned char *sha1)\n+{\n+\tstruct object *obj = parse_object(sha1);\n+\twhile (obj->type == tag_type) {\n+\t\tobj = ((struct tag *) obj)->tagged;\n+\t\tparse_object(obj->sha1);\n+\t}\n+\tif (obj->type == commit_type) {\n+\t\tobj->flags |= 1;\n+\t\tinsert_by_date((struct commit *) obj, &complete);\n+\t}\n+\treturn 0;\n+}\n \n int pull(char *target)\n {\n@@ -191,6 +213,8 @@ int pull(char *target)\n \t\t\treturn -1;\n \t}\n \n+\tfor_each_ref(mark_complete);\n+\n \tif (interpret_target(target, sha1))\n \t\treturn error(\"Could not interpret %s as something to pull\",\n \t\t\t     target);\n"},{"id":"8590","messageId":"7vd5naah1m.fsf@assigned-by-dhcp.cox.net","threadId":"1802","inReplyTo":"Pine.LNX.4.63.0509142120020.23242@iabervon.org","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-15T08:09:25Z","receivedAt":"2005-09-15T08:09:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow <barkalow@iabervon.org> writes:\n\n> Don't assume that any commit we have is complete; assume that any ref\n> we have is complete.\n>\n> Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n>\n> ---\n> Only lightly tested, but it seems to work. Marks all of the commits in \n> refs, and their ancestors back as far as the date of the commit it's \n> processing. If the commit it's processing is marked, it doesn't recurse \n> into it.\n\nFirst I thought you were using the date for the cutting-off\ndecision and was going to object to the patch because of it, but\nre-reading the code made me realize that you are using date only\nto better the heuristics that limits how many commits reachable\nfrom existing refs we would tangle to see if the newly seen\ncommit is reachable from our refs -- the logic looks correct.\n\nThe \"complete\" commit_list is a clever piece of code; I like it.\n"},{"id":"8597","messageId":"20050915150205.65378a65.vsu@altlinux.ru","threadId":"1802","inReplyTo":"Pine.LNX.4.63.0509142120020.23242@iabervon.org","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2005-09-15T11:02:05Z","receivedAt":"2005-09-15T11:02:05Z","isPatch":true,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"On Wed, 14 Sep 2005 21:31:42 -0400 (EDT) Daniel Barkalow wrote:\n\n> Don't assume that any commit we have is complete; assume that any ref\n> we have is complete.\n> \n> Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n> \n> ---\n> Only lightly tested, but it seems to work. Marks all of the commits in \n> refs, and their ancestors back as far as the date of the commit it's \n> processing. If the commit it's processing is marked, it doesn't recurse \n> into it.\n\nSeems to work here too (however, previous playing with git-fetch and\nold git-http-fetch left .git/refs/heads/origin.remote pointing to an\nincomplete commit, and this greatly confused the new git-http-fetch).\n\nJunio, probably you can throw away my patches adding --recover (also I\nforgot to add Signed-off-by for them...) - the automatic recovery\nprovided by this patch is better.  Still there is some room for\nimprovement...\n\n> This should make it very difficult to get it to produce a situation where \n> it completes without giving you complete information, and it shouldn't \n> process commits that are accessible from refs.\n> \n>  fetch.c |   28 ++++++++++++++++++++++++++--\n>  1 files changed, 26 insertions(+), 2 deletions(-)\n> \n> 39216139abc4f2759f7b55d11fa2f7e7c155898c\n> diff --git a/fetch.c b/fetch.c\n> --- a/fetch.c\n> +++ b/fetch.c\n> @@ -62,11 +62,21 @@ static int process_tree(struct tree *tre\n>  \treturn 0;\n>  }\n>  \n> +struct commit_list *complete = NULL;\n\nstatic\n\n> +\n>  static int process_commit(struct commit *commit)\n>  {\n>  \tif (parse_commit(commit))\n>  \t\treturn -1;\n>  \n> +\twhile (complete && complete->item->date >= commit->date) {\n> +\t\tpop_most_recent_commit(&complete, 1);\n> +\t}\n> +\t\t\n> +\n> +\tif (commit->object.flags & 1)\n> +\t\treturn 0;\n\nHmm, I would define some constant for this flag at the top of file:\n\n/* Object flags */\n#define COMPLETE\t(1U << 0)\n\nOtherwise it is hard to see what object flags are used in the code\n(only one flag is used currently, but we may need more in the future).\n\n> +\n>  \tmemcpy(current_commit_sha1, commit->object.sha1, 20);\n>  \n>  \tif (get_tree) {\n> @@ -78,8 +88,6 @@ static int process_commit(struct commit \n>  \tif (get_history) {\n>  \t\tstruct commit_list *parents = commit->parents;\n>  \t\tfor (; parents; parents = parents->next) {\n> -\t\t\tif (has_sha1_file(parents->item->object.sha1))\n> -\t\t\t\tcontinue;\n>  \t\t\tif (process(parents->item->object.sha1,\n>  \t\t\t\t    commit_type))\n>  \t\t\t\treturn -1;\n> @@ -126,6 +134,7 @@ static int process_object(struct object \n>  static int process(unsigned char *sha1, const char *type)\n>  {\n>  \tstruct object *obj = lookup_object_type(sha1, type);\n> +\n>  \tif (has_sha1_file(sha1)) {\n>  \t\tparse_object(sha1);\n>  \t\t/* We already have it, so we should scan it now. */\n> @@ -179,6 +188,19 @@ static int interpret_target(char *target\n>  \treturn -1;\n>  }\n>  \n> +static int mark_complete(const char *path, const unsigned char *sha1)\n> +{\n> +\tstruct object *obj = parse_object(sha1);\n> +\twhile (obj->type == tag_type) {\n> +\t\tobj = ((struct tag *) obj)->tagged;\n> +\t\tparse_object(obj->sha1);\n> +\t}\n> +\tif (obj->type == commit_type) {\n> +\t\tobj->flags |= 1;\n> +\t\tinsert_by_date((struct commit *) obj, &complete);\n> +\t}\n\nDereferencing of tags is already implemented:\n\n\tstruct commit *commit = lookup_commit_reference_gently(sha1, 1);\n\tif (commit) {\n\t\tcommit->object.flags |= 1;\n\t\tinsert_by_date(commit, &complete);\n\t}\n\n> +\treturn 0;\n> +}\n>  \n>  int pull(char *target)\n>  {\n> @@ -191,6 +213,8 @@ int pull(char *target)\n>  \t\t\treturn -1;\n>  \t}\n>  \n> +\tfor_each_ref(mark_complete);\n> +\n>  \tif (interpret_target(target, sha1))\n>  \t\treturn error(\"Could not interpret %s as something to pull\",\n>  \t\t\t     target);\n"},{"id":"8610","messageId":"Pine.LNX.4.63.0509151219590.23242@iabervon.org","threadId":"1802","inReplyTo":"7vd5naah1m.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-15T16:42:17Z","receivedAt":"2005-09-15T16:42:17Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 15 Sep 2005, Junio C Hamano wrote:\n\n> Daniel Barkalow <barkalow@iabervon.org> writes:\n> \n> > Don't assume that any commit we have is complete; assume that any ref\n> > we have is complete.\n> >\n> > Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n> >\n> > ---\n> > Only lightly tested, but it seems to work. Marks all of the commits in \n> > refs, and their ancestors back as far as the date of the commit it's \n> > processing. If the commit it's processing is marked, it doesn't recurse \n> > into it.\n> \n> First I thought you were using the date for the cutting-off\n> decision and was going to object to the patch because of it, but\n> re-reading the code made me realize that you are using date only\n> to better the heuristics that limits how many commits reachable\n> from existing refs we would tangle to see if the newly seen\n> commit is reachable from our refs -- the logic looks correct.\n> \n> The \"complete\" commit_list is a clever piece of code; I like it.\n\nIt's actually just the core loop of rev-list's original behavior. It's \nequivalent to putting the commit we're looking for in the list and popping \nthe list until it comes back out, except that it saves a bit of \nlist-fiddling. It's worth knowing that you can do rev-list (minus some of \nthe features for human-readability) integrated into your program with just \na couple of lines.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8611","messageId":"Pine.LNX.4.63.0509151243020.23242@iabervon.org","threadId":"1802","inReplyTo":"20050915150205.65378a65.vsu@altlinux.ru","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-15T16:54:44Z","receivedAt":"2005-09-15T16:54:44Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 15 Sep 2005, Sergey Vlasov wrote:\n\n> On Wed, 14 Sep 2005 21:31:42 -0400 (EDT) Daniel Barkalow wrote:\n> \n> > Don't assume that any commit we have is complete; assume that any ref\n> > we have is complete.\n> > \n> > Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n> > \n> > ---\n> > Only lightly tested, but it seems to work. Marks all of the commits in \n> > refs, and their ancestors back as far as the date of the commit it's \n> > processing. If the commit it's processing is marked, it doesn't recurse \n> > into it.\n> \n> Seems to work here too (however, previous playing with git-fetch and\n> old git-http-fetch left .git/refs/heads/origin.remote pointing to an\n> incomplete commit, and this greatly confused the new git-http-fetch).\n> \n> Junio, probably you can throw away my patches adding --recover (also I\n> forgot to add Signed-off-by for them...) - the automatic recovery\n> provided by this patch is better.  Still there is some room for\n> improvement...\n> \n> > This should make it very difficult to get it to produce a situation where \n> > it completes without giving you complete information, and it shouldn't \n> > process commits that are accessible from refs.\n> > \n> >  fetch.c |   28 ++++++++++++++++++++++++++--\n> >  1 files changed, 26 insertions(+), 2 deletions(-)\n> > \n> > 39216139abc4f2759f7b55d11fa2f7e7c155898c\n> > diff --git a/fetch.c b/fetch.c\n> > --- a/fetch.c\n> > +++ b/fetch.c\n> > @@ -62,11 +62,21 @@ static int process_tree(struct tree *tre\n> >  \treturn 0;\n> >  }\n> >  \n> > +struct commit_list *complete = NULL;\n> \n> static\n\nYup.\n\n> > +\tif (commit->object.flags & 1)\n> > +\t\treturn 0;\n> \n> Hmm, I would define some constant for this flag at the top of file:\n> \n> /* Object flags */\n> #define COMPLETE\t(1U << 0)\n> \n> Otherwise it is hard to see what object flags are used in the code\n> (only one flag is used currently, but we may need more in the future).\n\nYup.\n\n> > +static int mark_complete(const char *path, const unsigned char *sha1)\n> > +{\n> > +\tstruct object *obj = parse_object(sha1);\n> > +\twhile (obj->type == tag_type) {\n> > +\t\tobj = ((struct tag *) obj)->tagged;\n> > +\t\tparse_object(obj->sha1);\n> > +\t}\n> > +\tif (obj->type == commit_type) {\n> > +\t\tobj->flags |= 1;\n> > +\t\tinsert_by_date((struct commit *) obj, &complete);\n> > +\t}\n> \n> Dereferencing of tags is already implemented:\n> \n> \tstruct commit *commit = lookup_commit_reference_gently(sha1, 1);\n> \tif (commit) {\n> \t\tcommit->object.flags |= 1;\n> \t\tinsert_by_date(commit, &complete);\n> \t}\n\nYup. I think I want to untangle some of the functions in commit.c, though, \nbecause it wasn't sufficiently clear to me how those functions worked for \nme to actually use the right one.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8658","messageId":"7vslw5tuob.fsf@assigned-by-dhcp.cox.net","threadId":"1802","inReplyTo":"Pine.LNX.4.63.0509151243020.23242@iabervon.org","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-16T06:04:36Z","receivedAt":"2005-09-16T06:04:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow <barkalow@iabervon.org> writes:\n\n> Yup. I think I want to untangle some of the functions in commit.c, though, \n> because it wasn't sufficiently clear to me how those functions worked for \n> me to actually use the right one.\n\nSorry, *_gently was my fault.  The version without _gently was\nthere first, which issued its own complaints when it was fed a\nnon commit -- I presume that was OK for the purpose of whoever\nwrote it first, but was not very useful when the caller wanted\nto do its own \"oh, if it is not a commit then I'll do this other\nthing then\" decision.\n"},{"id":"8753","messageId":"7vhdckceas.fsf@assigned-by-dhcp.cox.net","threadId":"1802","inReplyTo":"Pine.LNX.4.63.0509142120020.23242@iabervon.org","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-17T08:02:35Z","receivedAt":"2005-09-17T08:02:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow <barkalow@iabervon.org> writes:\n\n> Don't assume that any commit we have is complete; assume that any ref\n> we have is complete.\n>\n> Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>\n>\n> ---\n> Only lightly tested, but it seems to work. Marks all of the commits in \n> refs, and their ancestors back as far as the date of the commit it's \n> processing. If the commit it's processing is marked, it doesn't recurse \n> into it.\n\nHave you tested this idea with cloning into an empty repository?\nIt seems to break my tests.\n"},{"id":"8755","messageId":"7vacicccxl.fsf@assigned-by-dhcp.cox.net","threadId":"1802","inReplyTo":"7vhdckceas.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Fix fetch completeness assumptions","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-17T08:32:06Z","receivedAt":"2005-09-17T08:32:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Daniel Barkalow <barkalow@iabervon.org> writes:\n>\n>> Don't assume that any commit we have is complete; assume that any ref\n>> we have is complete.\n>\n> Have you tested this idea with cloning into an empty repository?\n> It seems to break my tests.\n\nSorry, I spoke too fast.  This is not _broken_ per se, but is\njust slow.\n\nI tried to clone http://kernel.org/pub/scm/git.git/; bulk of the\nobjects are packed there but the new code is _too_ cautious,\nsince it did not have any refs to begin with, it ended up\nwalking the commits in the already downloaded packs to the root.\n"},{"id":"8756","messageId":"7vvf10axia.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1802","inReplyTo":"7vacicccxl.fsf@assigned-by-dhcp.cox.net","subject":"Help cloning over http.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-17T08:50:37Z","receivedAt":"2005-09-17T08:50:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Even when repository is packed, the new \"we trust only the refs\nwe already have\" code wasted too much time verifying what are\nalready in packs, walking down to the root commits.  Since we\nslurp all the necessary packs upfront and run verify pack on\nthem, temporarily register their edge commits as \"known to be\ngood\" before invoking git-http-fetch.\n\nI am not proud of this workaround -- this would probably break\nin a pathological case where the remote repository has packs\nthat depend on ancient unpacked objects, but people should not\nbe making such packs anyway (git repack would not create such\npacks).\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n git-clone.sh |   19 +++++++++++++++++++\n 1 files changed, 19 insertions(+), 0 deletions(-)\n\n34414e4170ab8d1d2a9ef582256530dc3b42d3e2\ndiff --git a/git-clone.sh b/git-clone.sh\n--- a/git-clone.sh\n+++ b/git-clone.sh\n@@ -50,11 +50,30 @@ Perhaps git-update-server-info needs to \n \t\tgit-verify-pack \".git/objects/pack/$idx\" || exit 1\n \tdone <\"$clone_tmp/packs\"\n \n+\twhile read type idx sha1 commit\n+\tdo\n+\t\tcase \"$type,$commit\" in\n+\t\tT,commit) ;;\n+\t\t*) continue ;;\n+\t\tesac &&\n+\t\techo \"$sha1\" >.git/refs/tags/clone-tmp-$sha1\n+\tdone <\"$clone_tmp/packs\"\n+\n \twhile read sha1 refname\n \tdo\n \t\tname=`expr \"$refname\" : 'refs/\\(.*\\)'` &&\n \t\tgit-http-fetch -v -a -w \"$name\" \"$name\" \"$1/\" || exit 1\n \tdone <\"$clone_tmp/refs\"\n+\n+\twhile read type idx sha1 commit\n+\tdo\n+\t\tcase \"$type,$commit\" in\n+\t\tT,commit) ;;\n+\t\t*) continue ;;\n+\t\tesac &&\n+\t\trm -f .git/refs/tags/clone-tmp-$sha1\n+\tdone <\"$clone_tmp/packs\"\n+\n \trm -fr \"$clone_tmp\"\n }\n \n"},{"id":"8765","messageId":"Pine.LNX.4.63.0509171235330.23242@iabervon.org","threadId":"1802","inReplyTo":"7vvf10axia.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Help cloning over http.","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-17T17:37:16Z","receivedAt":"2005-09-17T17:37:16Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Sat, 17 Sep 2005, Junio C Hamano wrote:\n\n> Even when repository is packed, the new \"we trust only the refs\n> we already have\" code wasted too much time verifying what are\n> already in packs, walking down to the root commits.  Since we\n> slurp all the necessary packs upfront and run verify pack on\n> them, temporarily register their edge commits as \"known to be\n> good\" before invoking git-http-fetch.\n\nThis is a somewhat special situation, because we're assuming that the \npacks are a complete set. When git-http-fetch downloads a pack, it still \nneeds to know if that pack uses other stuff, in which case it probably \nneeds to download it. The old code actually wouldn't have worked properly \nif the first pack didn't include any blobs that were still in the latest \nversion, because it wouldn't track commits through the pack and only \ngenerally worked with multiple packs because it would need blobs from \nevery pack to produce the current tree. \n\nI think that this gets particularly tricky with alternates, where the \nnecessary packs for ancient history may not actually be in the list of \npacks in the repository we're looking at.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8791","messageId":"7vbr2q46ow.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1802","inReplyTo":"Pine.LNX.4.63.0509171235330.23242@iabervon.org","subject":"[PATCH] Improve the safety check used in fetch.c","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-18T17:38:39Z","receivedAt":"2005-09-18T17:38:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The recent safety check to trust only the commits we have made\nthings impossibly slow and wastes a lot of memory.\n\nThis commit fixes it with the following improvements:\n\n - mark already scanned objects and avoid rescanning the same\n   object again;\n\n - free the tree entries when we have scanned the tree entries;\n   this is the same as b0d8923ec01fd91b75ab079034f89ced91500157\n   which reduced memory usage by rev-list;\n\n - plug memory leak from the object_list dequeuing code;\n\n - use the process_queue not just for fetching but for scanning,\n   to make things tail recursive to avoid deep recursion; the\n   deep recursion was especially prominent when we cloned a big\n   pack.\n\n - avoid has_sha1_file() call when we already know we do not have\n   that object.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n fetch.c |   76 ++++++++++++++++++++++++++++++++++++---------------------------\n 1 files changed, 44 insertions(+), 32 deletions(-)\n\n85d106c267ec26f398e0aaf352d8011f661c459a\ndiff --git a/fetch.c b/fetch.c\n--- a/fetch.c\n+++ b/fetch.c\n@@ -33,36 +33,33 @@ static void report_missing(const char *w\n \t\twhat, missing_hex, sha1_to_hex(current_commit_sha1));\n }\n \n-static int make_sure_we_have_it(const char *what, unsigned char *sha1)\n-{\n-\tint status = 0;\n-\n-\tif (!has_sha1_file(sha1)) {\n-\t\tstatus = fetch(sha1);\n-\t\tif (status && what)\n-\t\t\treport_missing(what, sha1);\n-\t}\n-\treturn status;\n-}\n-\n static int process(unsigned char *sha1, const char *type);\n \n static int process_tree(struct tree *tree)\n {\n-\tstruct tree_entry_list *entries;\n+\tstruct tree_entry_list *entry;\n \n \tif (parse_tree(tree))\n \t\treturn -1;\n \n-\tfor (entries = tree->entries; entries; entries = entries->next) {\n-\t\tif (process(entries->item.any->sha1,\n-\t\t\t    entries->directory ? tree_type : blob_type))\n+\tentry = tree->entries;\n+\ttree->entries = NULL;\n+\twhile (entry) {\n+\t\tstruct tree_entry_list *next = entry->next;\n+\t\tif (process(entry->item.any->sha1,\n+\t\t\t    entry->directory ? tree_type : blob_type))\n \t\t\treturn -1;\n+\t\tfree(entry);\n+\t\tentry = next;\n \t}\n \treturn 0;\n }\n \n #define COMPLETE\t1U\n+#define TO_FETCH\t2U\n+#define TO_SCAN\t\t4U\n+#define SCANNED\t\t8U\n+\n static struct commit_list *complete = NULL;\n \n static int process_commit(struct commit *commit)\n@@ -73,13 +70,14 @@ static int process_commit(struct commit \n \twhile (complete && complete->item->date >= commit->date) {\n \t\tpop_most_recent_commit(&complete, COMPLETE);\n \t}\n-\t\t\n \n \tif (commit->object.flags & COMPLETE)\n \t\treturn 0;\n \n \tmemcpy(current_commit_sha1, commit->object.sha1, 20);\n \n+\tpull_say(\"walk %s\\n\", sha1_to_hex(commit->object.sha1));\n+\n \tif (get_tree) {\n \t\tif (process(commit->tree->object.sha1, tree_type))\n \t\t\treturn -1;\n@@ -89,8 +87,7 @@ static int process_commit(struct commit \n \tif (get_history) {\n \t\tstruct commit_list *parents = commit->parents;\n \t\tfor (; parents; parents = parents->next) {\n-\t\t\tif (process(parents->item->object.sha1,\n-\t\t\t\t    commit_type))\n+\t\t\tif (process(parents->item->object.sha1, commit_type))\n \t\t\t\treturn -1;\n \t\t}\n \t}\n@@ -109,6 +106,10 @@ static struct object_list **process_queu\n \n static int process_object(struct object *obj)\n {\n+\tif (obj->flags & SCANNED)\n+\t\treturn 0;\n+\tobj->flags |= SCANNED;\n+\n \tif (obj->type == commit_type) {\n \t\tif (process_commit((struct commit *)obj))\n \t\t\treturn -1;\n@@ -139,14 +140,19 @@ static int process(unsigned char *sha1, \n \tif (has_sha1_file(sha1)) {\n \t\tparse_object(sha1);\n \t\t/* We already have it, so we should scan it now. */\n-\t\treturn process_object(obj);\n+\t\tif (obj->flags & (SCANNED | TO_SCAN))\n+\t\t\treturn 0;\n+\t\tobject_list_insert(obj, process_queue_end);\n+\t\tprocess_queue_end = &(*process_queue_end)->next;\n+\t\tobj->flags |= TO_SCAN;\n+\t\treturn 0;\n \t}\n-\tif (object_list_contains(process_queue, obj))\n+\tif (obj->flags & (COMPLETE | TO_FETCH))\n \t\treturn 0;\n \tobject_list_insert(obj, process_queue_end);\n \tprocess_queue_end = &(*process_queue_end)->next;\n+\tobj->flags |= TO_FETCH;\n \n-\t//fprintf(stderr, \"prefetch %s\\n\", sha1_to_hex(sha1));\n \tprefetch(sha1);\n \t\t\n \treturn 0;\n@@ -154,21 +160,27 @@ static int process(unsigned char *sha1, \n \n static int loop(void)\n {\n+\tstruct object_list *elem;\n+\n \twhile (process_queue) {\n \t\tstruct object *obj = process_queue->item;\n-\t\t/*\n-\t\tfprintf(stderr, \"%d objects to pull\\n\", \n-\t\t\tobject_list_length(process_queue));\n-\t\t*/\n-\t\tprocess_queue = process_queue->next;\n+\t\telem = process_queue;\n+\t\tprocess_queue = elem->next;\n+\t\tfree(elem);\n \t\tif (!process_queue)\n \t\t\tprocess_queue_end = &process_queue;\n \n-\t\t//fprintf(stderr, \"fetch %s\\n\", sha1_to_hex(obj->sha1));\n-\t\t\n-\t\tif (make_sure_we_have_it(obj->type ? obj->type : \"object\", \n-\t\t\t\t\t obj->sha1))\n-\t\t\treturn -1;\n+\t\t/* If we are not scanning this object, we placed it in\n+\t\t * the queue because we needed to fetch it first.\n+\t\t */\n+\t\tif (! (obj->flags & TO_SCAN)) {\n+\t\t\tif (fetch(obj->sha1)) {\n+\t\t\t\treport_missing(obj->type\n+\t\t\t\t\t       ? obj->type\n+\t\t\t\t\t       : \"object\", obj->sha1);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t}\n \t\tif (!obj->type)\n \t\t\tparse_object(obj->sha1);\n \t\tif (process_object(obj))\n"}]}