{"thread":{"id":"34673","subject":"git stash takes excessively long when many untracked files present","startedAt":"2013-08-10T21:44:55Z","lastAt":"2013-08-15T23:30:32Z","messageCount":15,"participants":["Josh Triplett","Anders Darander","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"225034","messageId":"20130810214453.GA5719@jtriplet-mobl1","threadId":"34673","inReplyTo":null,"subject":"git stash takes excessively long when many untracked files present","fromName":"Josh Triplett","fromEmail":"josh@joshtriplett.org","sentAt":"2013-08-10T21:44:55Z","receivedAt":"2013-08-10T21:44:55Z","isPatch":false,"sender":{"key":"josh@joshtriplett.org","avatar":"https://avatars.githubusercontent.com/u/162737?v=4"},"body":"[CCing folks involved in the recent \"stash-refuse-to-kill\" merge.]\n\nI keep portions of my home directory in git.  I tried to \"git stash\"\nsome local changes, and it ran for several minutes with no progress.  ps\nshowed that it was running \"git ls-files --killed\", which was taking\n100% CPU, and occasionally reading the disk very slowly.\n\nstrace shows that git ls-files --killed is doing a full recursive\nenumeration of my entire home directory.  That's a Really Bad Idea:\n\n~$ find | wc -l\n3248997\n~$ find -type d | wc -l\n350680\n\nNot only that, but it also appears to be attempting to stat and open\nseveral files in every single directory; for instance:\n\nstat(\".ccache/1/3/.git\", 0x7fff254bc7a0) = -1 ENOENT (No such file or directory)\nopen(\".ccache/1/3/.git/HEAD\", O_RDONLY) = -1 ENOENT (No such file or directory)\nstat(\".ccache/1/3/.git\", 0x7fff254bc770) = -1 ENOENT (No such file or directory)\nopen(\".ccache/1/3/.git/packed-refs\", O_RDONLY) = -1 ENOENT (No such file or directory)\n\n(Yes, in that order.)\n\nI see a lot of room for optimization here.  Most importantly, git\nls-files --killed really doesn't need to look at any directory entry\nunless something in the index would conflict with it.\n\n- Josh Triplett\n"},{"id":"225137","messageId":"loom.20130813T120243-481@post.gmane.org","threadId":"34673","inReplyTo":"20130810214453.GA5719@jtriplet-mobl1","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Anders Darander","fromEmail":"anders.darander@gmail.com","sentAt":"2013-08-13T10:11:11Z","receivedAt":"2013-08-13T10:11:11Z","isPatch":false,"sender":{"key":"anders.darander@gmail.com","avatar":null},"body":"Josh Triplett <josh <at> joshtriplett.org> writes:\n> [CCing folks involved in the recent \"stash-refuse-to-kill\" merge.]\n> \n> I keep portions of my home directory in git.  I tried to \"git stash\"\n> some local changes, and it ran for several minutes with no progress.  ps\n> showed that it was running \"git ls-files --killed\", which was taking\n> 100% CPU, and occasionally reading the disk very slowly.\n\nI've recently got the same problem, though in this case it's my \nopenembedded directory that's giving me those problems. (Having an \nuntracked build-directory of quiet a few GB takes some time).\n\nI worked around it by locally patching git-stash:\n-------------------------------------------\ndiff --git a/git-stash.sh b/git-stash.sh\nindex 85c9e2c..e5a2043 100755\n--- a/git-stash.sh\n+++ b/git-stash.sh\n@@ -263,7 +263,7 @@ save_stash () {\n                exit 0\n        fi\n        if test -z \"$untracked$force\" &&\n-          test -n \"$(git ls-files --killed | head -n 1)\"\n+          test -n \"$(git ls-files --killed --directory | head -n 1)\"\n        then\n                say \"$(gettext \"The following untracked files would NOT be \nsaved\n                test -n \"$GIT_QUIET\" || git ls-files --killed | sed \n's/^/\\t/'\n-------------------------------------------\n\nIt seems to work in my extremely limited testing. Though, I'm pretty sure \nthat there'll be quite a few error cases... (Especially, as I just made\na naive attempt at patching git-stash, so I could go on with a few other \nthings).\n\nDo anyone have any better idea on how to approach this?\n\n> strace shows that git ls-files --killed is doing a full recursive\n> enumeration of my entire home directory.  That's a Really Bad Idea:\n> \n> ~$ find | wc -l\n> 3248997\n> ~$ find -type d | wc -l\n> 350680\n> \n> Not only that, but it also appears to be attempting to stat and open\n> several files in every single directory; for instance:\n> \n> stat(\".ccache/1/3/.git\", 0x7fff254bc7a0) = -1 ENOENT (No such file or \ndirectory)\n> open(\".ccache/1/3/.git/HEAD\", O_RDONLY) = -1 ENOENT (No such file or \ndirectory)\n> stat(\".ccache/1/3/.git\", 0x7fff254bc770) = -1 ENOENT (No such file or \ndirectory)\n> open(\".ccache/1/3/.git/packed-refs\", O_RDONLY) = -1 ENOENT (No such file \nor directory)\n> \n> (Yes, in that order.)\n> \n> I see a lot of room for optimization here.  Most importantly, git\n> ls-files --killed really doesn't need to look at any directory entry\n> unless something in the index would conflict with it.\n\nI guess that this would be a good optimization. Or, are ls-files --killed \nused in other cases where the current behaviour would be requiered?\n\nCheers,\nAnders\n"},{"id":"225154","messageId":"7v7gfpy0wy.fsf@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"loom.20130813T120243-481@post.gmane.org","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-13T17:07:41Z","receivedAt":"2013-08-13T17:07:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Anders Darander <anders.darander@gmail.com> writes:\n\n> diff --git a/git-stash.sh b/git-stash.sh\n> index 85c9e2c..e5a2043 100755\n> --- a/git-stash.sh\n> +++ b/git-stash.sh\n> @@ -263,7 +263,7 @@ save_stash () {\n>                 exit 0\n>         fi\n>         if test -z \"$untracked$force\" &&\n> -          test -n \"$(git ls-files --killed | head -n 1)\"\n> +          test -n \"$(git ls-files --killed --directory | head -n 1)\"\n>         then\n>                 say \"$(gettext \"The following untracked files would NOT be \n> saved\n>                 test -n \"$GIT_QUIET\" || git ls-files --killed | sed \n> 's/^/\\t/'\n> -------------------------------------------\n>\n> It seems to work in my extremely limited testing. Though, I'm pretty sure \n> that there'll be quite a few error cases... (Especially, as I just made\n> a naive attempt at patching git-stash, so I could go on with a few other \n> things).\n\nI am not sure adding \"--directory\" there is safe.  Aren't there\ncases where saving a stash and going back to the committed state\nwill involve killing no directories, but some files?  If your local\nchange is to remove a directory and files in it from your working\ntree and then deposit a newly created file at the path where the\ndirectory was in the HEAD, stashing that local change and then going\nback to the HEAD will involve removing the new file from the working\ntree, and unless you have \"git add\"ed the new file, it will be lost.\n\n> Do anyone have any better idea on how to approach this?\n\nTeaching \"ls-files\" to leave early once it seens even a single\noutput is probably a possibility.\n\n>> I see a lot of room for optimization here.  Most importantly, git\n>> ls-files --killed really doesn't need to look at any directory entry\n>> unless something in the index would conflict with it.\n\nThis observation probably is correct, even though I didn't think\nabout it long enough.\n\nThanks.\n"},{"id":"225156","messageId":"1fc732a7-6b63-4d75-960f-0b1c6cf9c70e@email.android.com","threadId":"34673","inReplyTo":"7v7gfpy0wy.fsf@alter.siamese.dyndns.org","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Anders Darander","fromEmail":"anders.darander@gmail.com","sentAt":"2013-08-13T17:36:59Z","receivedAt":"2013-08-13T17:36:59Z","isPatch":false,"sender":{"key":"anders.darander@gmail.com","avatar":null},"body":"\n\n(I'm resending this as Gmail added some html parts...) \n\nJunio C Hamano <gitster@pobox.com> wrote:\n>Anders Darander <anders.darander@gmail.com> writes:\n>\n>> diff --git a/git-stash.sh b/git-stash.sh\n>> index 85c9e2c..e5a2043 100755\n>> --- a/git-stash.sh\n>> +++ b/git-stash.sh\n>> @@ -263,7 +263,7 @@ save_stash () {\n>>                 exit 0\n>>         fi\n>>         if test -z \"$untracked$force\" &&\n>> -          test -n \"$(git ls-files --killed | head -n 1)\"\n>> +          test -n \"$(git ls-files --killed --directory | head -n 1)\"\n>>         then\n>>                 say \"$(gettext \"The following untracked files would\n>NOT be \n>> saved\n>>                 test -n \"$GIT_QUIET\" || git ls-files --killed | sed \n>> 's/^/\\t/'\n>> -------------------------------------------\n>>\n>> It seems to work in my extremely limited testing. Though, I'm pretty\n>sure \n>> that there'll be quite a few error cases... (Especially, as I just\n>made\n>> a naive attempt at patching git-stash, so I could go on with a few\n>other \n>> things).\n>\n>I am not sure adding \"--directory\" there is safe.  Aren't there\n>cases where saving a stash and going back to the committed state\n>will involve killing no directories, but some files?  If your local\n>change is to remove a directory and files in it from your working\n>tree and then deposit a newly created file at the path where the\n>directory was in the HEAD, stashing that local change and then going\n>back to the HEAD will involve removing the new file from the working\n>tree, and unless you have \"git add\"ed the new file, it will be lost.\n\nYes, it's more than likely that there are some real issues with adding - -directory here. I just realised that in the specific case I needed to run stash, I could do that by adding either of -u or -f as options. Obviously, \n\n>> Do anyone have any better idea on how to approach this?\n>\n>Teaching \"ls-files\" to leave early once it seens even a single\n>output is probably a possibility.\n\nWould that mean that we're able to fail early? That's certainly an improvement, but not a working situation.\n\nIn my case, running stash in an OpenEmbedded checkout (including untracked directories for builds and caches), I gave up waiting on stash running ls-files after running at 100% for more than 12 minutes. Git status returned after a couple of seconds.\n\n>>> I see a lot of room for optimization here.  Most importantly, git\n>>> ls-files --killed really doesn't need to look at any directory entry\n>>> unless something in the index would conflict with it.\n>\n>This observation probably is correct, even though I didn't think\n>about it long enough.\n\nI'd think that something like this is needed. As the index should be rather small, compared to e.g. some large untracked directory.\n\nCheers, \nAnders \n\n\n.\n"},{"id":"225159","messageId":"7vmwolwk94.fsf@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"1fc732a7-6b63-4d75-960f-0b1c6cf9c70e@email.android.com","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-13T17:52:55Z","receivedAt":"2013-08-13T17:52:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Anders Darander <anders.darander@gmail.com> writes:\n\n>>> Do anyone have any better idea on how to approach this?\n>>\n>>Teaching \"ls-files\" to leave early once it seens even a single\n>>output is probably a possibility.\n>\n> Would that mean that we're able to fail early?\n\nHeh, good point.  \"Leave once you find one path\" does not help the\nmost common \"sane\" case where you do not kill any path, so it does\nnot help us at all.\n"},{"id":"225168","messageId":"7v61v9w9dy.fsf@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"7vmwolwk94.fsf@alter.siamese.dyndns.org","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-13T21:47:37Z","receivedAt":"2013-08-13T21:47:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"[administrivia: people on the original thread added back on CC]\n\nJunio C Hamano <gitster@pobox.com> writes:\n\n> Anders Darander <anders.darander@gmail.com> writes:\n>\n>>>> Do anyone have any better idea on how to approach this?\n>>>\n>>>Teaching \"ls-files\" to leave early once it seens even a single\n>>>output is probably a possibility.\n>>\n>> Would that mean that we're able to fail early?\n>\n> Heh, good point.  \"Leave once you find one path\" does not help the\n> most common \"sane\" case where you do not kill any path, so it does\n> not help us at all.\n\nIn any case, this is a regression introduced in 'master' since the\nlast release, and the attempted fix was for an issue that has long\nbeen with us, so I'll revert a7365313 (git stash: avoid data loss\nwhen \"git stash save\" kills a directory, 2013-06-28) soon.  For\ntoday's -rc3, I'm already deep into the integration cycle, so it is\ntoo late to do the revert it and then redo everything.\n\nThen we will plan to re-apply the patch once \"ls-files --killed\"\ngets fixed not to waste too much cycles needlessly, after the coming\nrelease.\n\nThanks for a report and discussion.\n"},{"id":"225270","messageId":"7vr4durgd4.fsf@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"7v61v9w9dy.fsf@alter.siamese.dyndns.org","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T17:52:39Z","receivedAt":"2013-08-15T17:52:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> In any case, this is a regression introduced in 'master' since the\n> last release, and the attempted fix was for an issue that has long\n> been with us, so I'll revert a7365313 (git stash: avoid data loss\n> when \"git stash save\" kills a directory, 2013-06-28) soon.  For\n> today's -rc3, I'm already deep into the integration cycle, so it is\n> too late to do the revert it and then redo everything.\n>\n> Then we will plan to re-apply the patch once \"ls-files --killed\"\n> gets fixed not to waste too much cycles needlessly, after the coming\n> release.\n\nI've already reverted the problematic patch to \"git stash\" and it\nwill not be part of the upcoming release.\n\nHere is a quick attempt to see if we can do better in \"ls-files -k\".\n\nWe have an existing test t3010.3 that tries all the combinations of\ndirectory turning into a regular file, symlink, etc. and vice versa,\nand it seems to pass.  The test has a directory path6 in the working\ntree without any paths in it in the index, and the added bypass code\nseems to correctly trigger and prevents us from digging into that\ndirectory, so this patch may be sufficient to improve \"ls-files -k\".\n\nBy the way, regarding the reverted commit, I do not think it is\nenough to ask \"ls-files -k\" to see if the state recorded in the\ncurrent index is sufficient.  Imagine your HEAD records \"path\" as a\nfile and then you did this:\n\n    $ git reset --hard ;# \"path\" is now a regular file\n    $ mv path path.bak\n    $ mkdir path\n    $ mv path.bak path/file\n    $ git add -A ;# \"path/file\" in the index and in the working tree\n    $ >path/cruft ;# \"path/cruft\" in the working tree\n\nThen call \"save_stash\" without saving untracked.  The resulting\nstash will save the contents of \"path/file\" but \"path/cruft\" is not\nrecorded anywhere, and then we would need to bring the state in the\nworking tree and the index back to the state recorded in HEAD, hence\n\"path\" needs to be turned back to a directory.\n\nBut \"ls-files -k\" is asked to check with the index, which has the\npath as a directory, so this case is missed.\n\nSo instead of\n\n\ttest -n \"$(git ls-files --killed | head -n 1)\"\n\nin Pasky's patch, which probably is a right thing to do if you are\nrunning \"git stash save --keep-index\", you would need something like\nthis if you are not running with \"--keep-index\":\n\n\ttest -n \"$(\n        \tGIT_INDEX_FILE=tmp_index\n                export GIT_INDEX_FILE\n                git read-tree HEAD\n                git ls-files -k\n\t)\"\n\nin order to make sure that the result of going back to the state in\nthe HEAD will not clobber leftover \"path/cruft\".\n\n builtin/ls-files.c | 2 ++\n dir.c              | 9 +++++++++\n dir.h              | 3 ++-\n 3 files changed, 13 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex 5cf3e31..8500446 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -219,6 +219,8 @@ static void show_files(struct dir_struct *dir)\n \n \t/* For cached/deleted files we don't need to even do the readdir */\n \tif (show_others || show_killed) {\n+\t\tif (!show_others)\n+\t\t\tdir->flags |= DIR_COLLECT_KILLED_ONLY;\n \t\tfill_directory(dir, pathspec);\n \t\tif (show_others)\n \t\t\tshow_other_files(dir);\ndiff --git a/dir.c b/dir.c\nindex 910bfcd..02939e2 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -1183,6 +1183,15 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t    cache_name_exists(path->buf, path->len, ignore_case))\n \t\treturn path_none;\n \n+\t/*\n+\t * A directory can only contain killed files if the index\n+\t * has a path that wants it to be a non-directory.\n+\t */\n+\tif ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&\n+\t    (dtype == DT_DIR) &&\n+\t    !cache_name_exists(path->buf, path->len, ignore_case))\n+\t\treturn path_none;\n+\n \texclude = is_excluded(dir, path->buf, &dtype);\n \n \t/*\ndiff --git a/dir.h b/dir.h\nindex 3d6b80c..4677b86 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -80,7 +80,8 @@ struct dir_struct {\n \t\tDIR_HIDE_EMPTY_DIRECTORIES = 1<<2,\n \t\tDIR_NO_GITLINKS = 1<<3,\n \t\tDIR_COLLECT_IGNORED = 1<<4,\n-\t\tDIR_SHOW_IGNORED_TOO = 1<<5\n+\t\tDIR_SHOW_IGNORED_TOO = 1<<5,\n+\t\tDIR_COLLECT_KILLED_ONLY = 1<<6\n \t} flags;\n \tstruct dir_entry **entries;\n \tstruct dir_entry **ignored;\n"},{"id":"225271","messageId":"20130815180736.GA4093@jtriplet-mobl1","threadId":"34673","inReplyTo":"7vr4durgd4.fsf@alter.siamese.dyndns.org","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Josh Triplett","fromEmail":"josh@joshtriplett.org","sentAt":"2013-08-15T18:07:36Z","receivedAt":"2013-08-15T18:07:36Z","isPatch":false,"sender":{"key":"josh@joshtriplett.org","avatar":"https://avatars.githubusercontent.com/u/162737?v=4"},"body":"On Thu, Aug 15, 2013 at 10:52:39AM -0700, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > In any case, this is a regression introduced in 'master' since the\n> > last release, and the attempted fix was for an issue that has long\n> > been with us, so I'll revert a7365313 (git stash: avoid data loss\n> > when \"git stash save\" kills a directory, 2013-06-28) soon.  For\n> > today's -rc3, I'm already deep into the integration cycle, so it is\n> > too late to do the revert it and then redo everything.\n> >\n> > Then we will plan to re-apply the patch once \"ls-files --killed\"\n> > gets fixed not to waste too much cycles needlessly, after the coming\n> > release.\n> \n> I've already reverted the problematic patch to \"git stash\" and it\n> will not be part of the upcoming release.\n\nThanks!\n\n> Here is a quick attempt to see if we can do better in \"ls-files -k\".\n> \n> We have an existing test t3010.3 that tries all the combinations of\n> directory turning into a regular file, symlink, etc. and vice versa,\n> and it seems to pass.  The test has a directory path6 in the working\n> tree without any paths in it in the index, and the added bypass code\n> seems to correctly trigger and prevents us from digging into that\n> directory, so this patch may be sufficient to improve \"ls-files -k\".\n> \n> By the way, regarding the reverted commit, I do not think it is\n> enough to ask \"ls-files -k\" to see if the state recorded in the\n> current index is sufficient.  Imagine your HEAD records \"path\" as a\n> file and then you did this:\n> \n>     $ git reset --hard ;# \"path\" is now a regular file\n>     $ mv path path.bak\n>     $ mkdir path\n>     $ mv path.bak path/file\n>     $ git add -A ;# \"path/file\" in the index and in the working tree\n>     $ >path/cruft ;# \"path/cruft\" in the working tree\n> \n> Then call \"save_stash\" without saving untracked.  The resulting\n> stash will save the contents of \"path/file\" but \"path/cruft\" is not\n> recorded anywhere, and then we would need to bring the state in the\n> working tree and the index back to the state recorded in HEAD, hence\n> \"path\" needs to be turned back to a directory.\n> \n> But \"ls-files -k\" is asked to check with the index, which has the\n> path as a directory, so this case is missed.\n\nSince git stash resets to the state in HEAD, whatever --killed check it\ndoes needs to check against HEAD, yes.  It still doesn't need to check\nany path that doesn't exist in HEAD, though; it makes more sense to\ndrive this from the list of files in HEAD rather than from the list of\nfiles in the working directory, even with a filter applied to the latter\nto prune bits not in HEAD.\n\n> So instead of\n> \n> \ttest -n \"$(git ls-files --killed | head -n 1)\"\n> \n> in Pasky's patch, which probably is a right thing to do if you are\n> running \"git stash save --keep-index\", you would need something like\n> this if you are not running with \"--keep-index\":\n> \n> \ttest -n \"$(\n>         \tGIT_INDEX_FILE=tmp_index\n>                 export GIT_INDEX_FILE\n>                 git read-tree HEAD\n>                 git ls-files -k\n> \t)\"\n> \n> in order to make sure that the result of going back to the state in\n> the HEAD will not clobber leftover \"path/cruft\".\n\nSure, that works.  However, wouldn't it make sense to just directly let\ngit ls-files output to the screen, then test its return value (after\nadding some ls-files option to set the return value)?  Since ls-files\n--killed will have no output if git stash can proceed, and since git\nstash should show the list of files that'd be killed before it fails,\nusing the output directly makes sense.\n\n- Josh Triplett\n"},{"id":"225276","messageId":"7vioz6rdba.fsf@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"20130815180736.GA4093@jtriplet-mobl1","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T18:58:33Z","receivedAt":"2013-08-15T18:58:33Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Josh Triplett <josh@joshtriplett.org> writes:\n\n>> I've already reverted the problematic patch to \"git stash\" and it\n>> will not be part of the upcoming release.\n>\n> Thanks!\n>\n>> Here is a quick attempt to see if we can do better in \"ls-files -k\".\n\nHaving said that, I am curious if the result of applying the patch\nyou are responding to, without reverting the \"git stash\" patch, is\nnow usable in the working tree you earlier had trouble with.\n\n> Sure, that works.  However, wouldn't it make sense to just directly let\n> git ls-files output to the screen, then test its return value (after\n> adding some ls-files option to set the return value)?\n\nNot really.\n\nWe may want to add \"exit early if we see even a single killed file\"\noption to the command so that we can simplify the \"are we going to\nabort\" logic, but the error codepath that is executed after that\ndecision is made is not performance critical, and may need more\nflexibility than always spewing everything that will be killed,\nwhich could be thousands of crufts.  So I think using two separate\ninvocations to \"ls-files --killed\" is a necessity anyway.\n"},{"id":"225280","messageId":"7v8v02rb2g.fsf@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"7vr4durgd4.fsf@alter.siamese.dyndns.org","subject":"Re: git stash takes excessively long when many untracked files present","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T19:47:03Z","receivedAt":"2013-08-15T19:47:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> diff --git a/dir.c b/dir.c\n> index 910bfcd..02939e2 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -1183,6 +1183,15 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n>  \t    cache_name_exists(path->buf, path->len, ignore_case))\n>  \t\treturn path_none;\n>  \n> +\t/*\n> +\t * A directory can only contain killed files if the index\n> +\t * has a path that wants it to be a non-directory.\n> +\t */\n> +\tif ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&\n> +\t    (dtype == DT_DIR) &&\n> +\t    !cache_name_exists(path->buf, path->len, ignore_case))\n> +\t\treturn path_none;\n> +\n\nI think this is wrong.\n\nWhen we are looking at a directory P in the working tree, there are\nthree cases:\n\n (1) P exists in the index.  Everything inside the directory P in\n     the working tree needs to go when P is checked out from the\n     index.\n\n (2) P does not exist in the index, but there is P/Q in the index.\n     We know P will stay a directory when we check out the contents\n     of the index, but we do not know yet if there is a directory\n     P/Q in the working tree to be killed, so we need to recurse.\n\n (3) P does not exist in the index, and there is no P/Q in the index\n     to require P to be a directory, either.  Only in this case, we\n     know that everything inside P will not be killed without\n     recursing.\n\nThe patch will break with the second case, I think.\n"},{"id":"225284","messageId":"1376602090-19142-1-git-send-email-gitster@pobox.com","threadId":"34673","inReplyTo":"7v8v02rb2g.fsf@alter.siamese.dyndns.org","subject":"[PATCH 0/3] Optimizing \"ls-files -k\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T21:28:07Z","receivedAt":"2013-08-15T21:28:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"ls-files -o\" and \"ls-files -k\" both traverse the working tree down\nto find either all untracked paths or those that will be \"killed\"\n(removed from the working tree to make room) when the paths recorded\nin the index are checked out.\n\nIt is necessary to traverse the working tree fully when enumerating\nall the \"other\" paths, but when we are only interested in \"killed\"\npaths, we can take advantage of the fact that paths that do not\noverlap with entries in the index can never be killed.\n\nThe first one is an independent clean-up.  No public API in the\nworking tree traversal takes alternate in-core index, so there is no\nreason to explicitly use the_index and index_* functions from the\nin-core index API.\n\nThe second one is rerolled from the \"something like this\" patch I\nsent earlier, but corrects the \"we see a directory, it is not in the\nindex, but a file in it is\" case.\n\nAnd the third one adds a testcase that illustrates why the earlier\n\"something like this\" patch is not sufficient.\n\nThese are designed to apply on top of v1.8.3, and needs a bit of\nconflict resolution for the upcoming v1.8.4 codebase; I'll queue\nthem in 'pu' for now.\n\nNote that t3010, especially after merged to 'pu', will use many\ndifferent ways to create a test file.  Some redirect \"date\" into it,\nsome redirect \":\" into it, some \"touch\" it, and some just redirect\nwith no command.\n\n\tdate >file1\n\t: >file2\n\ttouch file3\n\t>file4\n\nWe should consolidate them all to just do \">file4\" after making sure\nthe contents do not matter (we kind of know it already, as \"date\"\nwill output string that is not repeatable).  Use of \"touch\" for\nanything other than updating the timestamp is especially bad, as it\nis misleading.\n\nJunio C Hamano (3):\n  dir.c: use the cache_* macro to access the current index\n  ls-files -k: a directory only can be killed if the index has a non-directory\n  t3010: update to demonstrate \"ls-files -k\" optimization pitfalls\n\n builtin/ls-files.c                  |  2 ++\n dir.c                               | 40 +++++++++++++++++++++++++++++--------\n dir.h                               |  3 ++-\n t/t3010-ls-files-killed-modified.sh | 12 ++++++++---\n 4 files changed, 45 insertions(+), 12 deletions(-)\n\n-- \n1.8.4-rc3-232-ga8053f8\n"},{"id":"225285","messageId":"1376602090-19142-2-git-send-email-gitster@pobox.com","threadId":"34673","inReplyTo":"1376602090-19142-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/3] dir.c: use the cache_* macro to access the current index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T21:28:08Z","receivedAt":"2013-08-15T21:28:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"These codepaths always start from the_index and use index_*\nfunctions, but there is no reason to do so.  Use the compatibility\ncache_* macro to access the current in-core index like everybody\nelse.\n\nWhile at it, fix typo in the comment for a function to check if a\npath within a directory appears in the index.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n dir.c | 11 +++++------\n 1 file changed, 5 insertions(+), 6 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex a5926fb..2f82cd1 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -472,15 +472,14 @@ static void *read_skip_worktree_file_from_index(const char *path, size_t *size)\n \tunsigned long sz;\n \tenum object_type type;\n \tvoid *data;\n-\tstruct index_state *istate = &the_index;\n \n \tlen = strlen(path);\n-\tpos = index_name_pos(istate, path, len);\n+\tpos = cache_name_pos(path, len);\n \tif (pos < 0)\n \t\treturn NULL;\n-\tif (!ce_skip_worktree(istate->cache[pos]))\n+\tif (!ce_skip_worktree(active_cache[pos]))\n \t\treturn NULL;\n-\tdata = read_sha1_file(istate->cache[pos]->sha1, &type, &sz);\n+\tdata = read_sha1_file(active_cache[pos]->sha1, &type, &sz);\n \tif (!data || type != OBJ_BLOB) {\n \t\tfree(data);\n \t\treturn NULL;\n@@ -924,13 +923,13 @@ enum exist_status {\n };\n \n /*\n- * Do not use the alphabetically stored index to look up\n+ * Do not use the alphabetically sorted index to look up\n  * the directory name; instead, use the case insensitive\n  * name hash.\n  */\n static enum exist_status directory_exists_in_index_icase(const char *dirname, int len)\n {\n-\tstruct cache_entry *ce = index_name_exists(&the_index, dirname, len + 1, ignore_case);\n+\tstruct cache_entry *ce = cache_name_exists(dirname, len + 1, ignore_case);\n \tunsigned char endchar;\n \n \tif (!ce)\n-- \n1.8.4-rc3-232-ga8053f8\n"},{"id":"225287","messageId":"1376602090-19142-3-git-send-email-gitster@pobox.com","threadId":"34673","inReplyTo":"1376602090-19142-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/3] ls-files -k: a directory only can be killed if the index has a non-directory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T21:28:09Z","receivedAt":"2013-08-15T21:28:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"ls-files -o\" and \"ls-files -k\" both traverse the working tree down\nto find either all untracked paths or those that will be \"killed\"\n(removed from the working tree to make room) when the paths recorded\nin the index are checked out.  It is necessary to traverse the\nworking tree fully when enumerating all the \"other\" paths, but when\nwe are only interested in \"killed\" paths, we can take advantage of\nthe fact that paths that do not overlap with entries in the index\ncan never be killed.\n\nThe treat_one_path() helper function, which is called during the\nrecursive traversal, is the ideal place to implement an\noptimization.\n\nWhen we are looking at a directory P in the working tree, there are\nthree cases:\n\n (1) P exists in the index.  Everything inside the directory P in\n     the working tree needs to go when P is checked out from the\n     index.\n\n (2) P does not exist in the index, but there is P/Q in the index.\n     We know P will stay a directory when we check out the contents\n     of the index, but we do not know yet if there is a directory\n     P/Q in the working tree to be killed, so we need to recurse.\n\n (3) P does not exist in the index, and there is no P/Q in the index\n     to require P to be a directory, either.  Only in this case, we\n     know that everything inside P will not be killed without\n     recursing.\n\nNote that this helper is called by treat_leading_path() that decides\nif we need to traverse only subdirectories of a single common\nleading directory, which is essential for this optimization to be\ncorrect.  This caller checks each level of the leading path\ncomponent from shallower directory to deeper ones, and that is what\nallows us to only check if the path appears in the index.  If the\ncall to treat_one_path() weren't there, given a path P/Q/R, the real\ntraversal may start from directory P/Q/R, even when the index\nrecords P as a regular file, and we would end up having to check if\nany leading subpath in P/Q/R, e.g. P, appears in the index.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/ls-files.c |  2 ++\n dir.c              | 29 +++++++++++++++++++++++++++--\n dir.h              |  3 ++-\n 3 files changed, 31 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex 2202072..c7eb6f4 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -213,6 +213,8 @@ static void show_files(struct dir_struct *dir)\n \n \t/* For cached/deleted files we don't need to even do the readdir */\n \tif (show_others || show_killed) {\n+\t\tif (!show_others)\n+\t\t\tdir->flags |= DIR_COLLECT_KILLED_ONLY;\n \t\tfill_directory(dir, pathspec);\n \t\tif (show_others)\n \t\t\tshow_other_files(dir);\ndiff --git a/dir.c b/dir.c\nindex 2f82cd1..ff768f3 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -1173,12 +1173,37 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t\t\t\t\t  int dtype, struct dirent *de)\n {\n \tint exclude;\n+\tint has_path_in_index = !!cache_name_exists(path->buf, path->len, ignore_case);\n+\n \tif (dtype == DT_UNKNOWN)\n \t\tdtype = get_dtype(de, path->buf, path->len);\n \n \t/* Always exclude indexed files */\n-\tif (dtype != DT_DIR &&\n-\t    cache_name_exists(path->buf, path->len, ignore_case))\n+\tif (dtype != DT_DIR && has_path_in_index)\n+\t\treturn path_none;\n+\n+\t/*\n+\t * When we are looking at a directory P in the working tree,\n+\t * there are three cases:\n+\t *\n+\t * (1) P exists in the index.  Everything inside the directory P in\n+\t * the working tree needs to go when P is checked out from the\n+\t * index.\n+\t *\n+\t * (2) P does not exist in the index, but there is P/Q in the index.\n+\t * We know P will stay a directory when we check out the contents\n+\t * of the index, but we do not know yet if there is a directory\n+\t * P/Q in the working tree to be killed, so we need to recurse.\n+\t *\n+\t * (3) P does not exist in the index, and there is no P/Q in the index\n+\t * to require P to be a directory, either.  Only in this case, we\n+\t * know that everything inside P will not be killed without\n+\t * recursing.\n+\t */\n+\tif ((dir->flags & DIR_COLLECT_KILLED_ONLY) &&\n+\t    (dtype == DT_DIR) &&\n+\t    !has_path_in_index &&\n+\t    (directory_exists_in_index(path->buf, path->len) == index_nonexistent))\n \t\treturn path_none;\n \n \texclude = is_excluded(dir, path->buf, &dtype);\ndiff --git a/dir.h b/dir.h\nindex 3d6b80c..4677b86 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -80,7 +80,8 @@ struct dir_struct {\n \t\tDIR_HIDE_EMPTY_DIRECTORIES = 1<<2,\n \t\tDIR_NO_GITLINKS = 1<<3,\n \t\tDIR_COLLECT_IGNORED = 1<<4,\n-\t\tDIR_SHOW_IGNORED_TOO = 1<<5\n+\t\tDIR_SHOW_IGNORED_TOO = 1<<5,\n+\t\tDIR_COLLECT_KILLED_ONLY = 1<<6\n \t} flags;\n \tstruct dir_entry **entries;\n \tstruct dir_entry **ignored;\n-- \n1.8.4-rc3-232-ga8053f8\n"},{"id":"225286","messageId":"1376602090-19142-4-git-send-email-gitster@pobox.com","threadId":"34673","inReplyTo":"1376602090-19142-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/3] t3010: update to demonstrate \"ls-files -k\" optimization pitfalls","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T21:28:10Z","receivedAt":"2013-08-15T21:28:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"An earlier draft of the previous step used cache_name_exists() to\ncheck the directory we were looking at, which missed the second case\ndescribed in its log message.  Demonstrate why it is not sufficient.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n t/t3010-ls-files-killed-modified.sh | 12 +++++++++---\n 1 file changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/t/t3010-ls-files-killed-modified.sh b/t/t3010-ls-files-killed-modified.sh\nindex 95671c2..6ea7ca8 100755\n--- a/t/t3010-ls-files-killed-modified.sh\n+++ b/t/t3010-ls-files-killed-modified.sh\n@@ -11,6 +11,7 @@ This test prepares the following in the cache:\n     path1       - a symlink\n     path2/file2 - a file in a directory\n     path3/file3 - a file in a directory\n+    pathx/ju    - a file in a directory\n \n and the following on the filesystem:\n \n@@ -21,6 +22,7 @@ and the following on the filesystem:\n     path4\t- a file\n     path5\t- a symlink\n     path6/file6 - a file in a directory\n+    pathx/ju/nk - a file in a directory to be killed\n \n git ls-files -k should report that existing filesystem\n objects except path4, path5 and path6/file6 to be killed.\n@@ -44,16 +46,17 @@ then\n else\n \tdate > path1\n fi\n-mkdir path2 path3\n+mkdir path2 path3 pathx\n date >path2/file2\n date >path3/file3\n+>pathx/ju\n : >path7\n date >path8\n : >path9\n date >path10\n test_expect_success \\\n     'git update-index --add to add various paths.' \\\n-    \"git update-index --add -- path0 path1 path?/file? path7 path8 path9 path10\"\n+    \"git update-index --add -- path0 path1 path?/file? pathx/ju path7 path8 path9 path10\"\n \n rm -fr path? ;# leave path10 alone\n date >path2\n@@ -65,7 +68,7 @@ else\n \tdate > path3\n \tdate > path5\n fi\n-mkdir path0 path1 path6\n+mkdir -p path0 path1 path6 pathx/ju\n date >path0/file0\n date >path1/file1\n date >path6/file6\n@@ -73,6 +76,7 @@ date >path7\n : >path8\n : >path9\n touch path10\n+>pathx/ju/nk\n \n test_expect_success \\\n     'git ls-files -k to show killed files.' \\\n@@ -82,6 +86,7 @@ path0/file0\n path1/file1\n path2\n path3\n+pathx/ju/nk\n EOF\n \n test_expect_success \\\n@@ -98,6 +103,7 @@ path2/file2\n path3/file3\n path7\n path8\n+pathx/ju\n EOF\n \n test_expect_success \\\n-- \n1.8.4-rc3-232-ga8053f8\n"},{"id":"225301","messageId":"7vli42o7l3.fsf_-_@alter.siamese.dyndns.org","threadId":"34673","inReplyTo":"1376602090-19142-1-git-send-email-gitster@pobox.com","subject":"[PATCH 4/3] git stash: avoid data loss when \"git stash save\" kills a directory","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-15T23:30:32Z","receivedAt":"2013-08-15T23:30:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"From: Petr Baudis <pasky@ucw.cz>\n\n\"stash save\" is about saving the local change to the working tree,\nbut also about restoring the state of the last commit to the working\ntree.  When a local change is to turn a non-directory to a directory,\nin order to restore the non-directory, everything in the directory\nneeds to be removed.\n\nWhich is fine when running \"git stash save --include-untracked\",\nbut without that option, untracked, newly created files in the\ndirectory will have to be discarded, if the state you are restoring\nto has a non-directory at the same path as the directory.\n\nIntroduce a safety valve to fail the operation in such case, using\nthe \"ls-files --killed\" which was designed for this exact purpose.\n\nThe \"stash save\" is stopped when untracked files need to be\ndiscarded because their leading path ceased to be a directory, and\nthe user is required to pass --force to really have the data\nremoved.\n\nSigned-off-by: Petr Baudis <pasky@ucw.cz>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * And this is the reverted patch ported on top of the \"ls-files -k\"\n   miniseries I sent earlier.  The updates to the test in t3903\n   compared to the original illustrates that the check implemented\n   in the original did not protect once a path that was turned into\n   a directory from a file gets added to the index, which this round\n   also fixes by running \"ls-files -k\" against the state in the HEAD.\n\n Documentation/git-stash.txt | 11 +++++++++--\n git-stash.sh                | 20 ++++++++++++++++++++\n t/t3903-stash.sh            | 22 ++++++++++++++++++++++\n 3 files changed, 51 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-stash.txt b/Documentation/git-stash.txt\nindex 711ffe1..61fadc5 100644\n--- a/Documentation/git-stash.txt\n+++ b/Documentation/git-stash.txt\n@@ -14,7 +14,7 @@ SYNOPSIS\n 'git stash' ( pop | apply ) [--index] [-q|--quiet] [<stash>]\n 'git stash' branch <branchname> [<stash>]\n 'git stash' [save [--patch] [-k|--[no-]keep-index] [-q|--quiet]\n-\t     [-u|--include-untracked] [-a|--all] [<message>]]\n+\t     [-u|--include-untracked] [-a|--all] [-f|--force] [<message>]]\n 'git stash' clear\n 'git stash' create\n \n@@ -43,7 +43,7 @@ is also possible).\n OPTIONS\n -------\n \n-save [-p|--patch] [--[no-]keep-index] [-u|--include-untracked] [-a|--all] [-q|--quiet] [<message>]::\n+save [-p|--patch] [--[no-]keep-index] [-u|--include-untracked] [-a|--all] [-q|--quiet] [-f|--force] [<message>]::\n \n \tSave your local modifications to a new 'stash', and run `git reset\n \t--hard` to revert them.  The <message> part is optional and gives\n@@ -70,6 +70,13 @@ linkgit:git-add[1] to learn how to operate the `--patch` mode.\n +\n The `--patch` option implies `--keep-index`.  You can use\n `--no-keep-index` to override this.\n++\n+In some cases, saving a stash could mean irretrievably removing some\n+data - if a directory with untracked files replaces a tracked file of\n+the same name, the new untracked files are not saved (except in case\n+of `--include-untracked`) but the original tracked file shall be restored.\n+By default, `stash save` will abort in such a case; `--force` will allow\n+it to remove the untracked files.\n \n list [<options>]::\n \ndiff --git a/git-stash.sh b/git-stash.sh\nindex bbefdf6..2d539f3 100755\n--- a/git-stash.sh\n+++ b/git-stash.sh\n@@ -156,10 +156,19 @@ create_stash () {\n \tdie \"$(gettext \"Cannot record working tree state\")\"\n }\n \n+# This helper MUST be run inside a subshell.\n+list_killed_files () {\n+\tGIT_INDEX_FILE=$TMP-ls-files-k &&\n+\texport GIT_INDEX_FILE &&\n+\tgit read-tree HEAD &&\n+\tgit ls-files --killed\n+}\n+\n save_stash () {\n \tkeep_index=\n \tpatch_mode=\n \tuntracked=\n+\tforce=\n \twhile test $# != 0\n \tdo\n \t\tcase \"$1\" in\n@@ -180,6 +189,9 @@ save_stash () {\n \t\t-u|--include-untracked)\n \t\t\tuntracked=untracked\n \t\t\t;;\n+\t\t-f|--force)\n+\t\t\tforce=t\n+\t\t\t;;\n \t\t-a|--all)\n \t\t\tuntracked=all\n \t\t\t;;\n@@ -223,6 +235,14 @@ save_stash () {\n \t\tsay \"$(gettext \"No local changes to save\")\"\n \t\texit 0\n \tfi\n+\tif test -z \"$untracked$force\" &&\n+\t   test -n \"$(list_killed_files | head -n 1)\"\n+\tthen\n+\t\tsay \"$(gettext \"The following untracked files would NOT be saved but need to be removed by stash save:\")\"\n+\t\ttest -n \"$GIT_QUIET\" || (list_killed_files | sed 's/^/\\t/')\n+\t\tsay \"$(gettext \"Aborting. Consider using either the --force or --include-untracked option.\")\" >&2\n+\t\texit 1\n+\tfi\n \ttest -f \"$GIT_DIR/logs/$ref_stash\" ||\n \t\tclear_stash || die \"$(gettext \"Cannot initialize stash\")\"\n \ndiff --git a/t/t3903-stash.sh b/t/t3903-stash.sh\nindex 5dfbda7..08ce23b 100755\n--- a/t/t3903-stash.sh\n+++ b/t/t3903-stash.sh\n@@ -637,4 +637,26 @@ test_expect_success 'stash where working directory contains \"HEAD\" file' '\n \ttest_cmp output expect\n '\n \n+test_expect_success 'stash a change to turn a non-directory to a directory' '\n+\tgit reset --hard &&\n+\t>testfile &&\n+\tgit add testfile &&\n+\tgit commit -m \"add testfile as a regular file\" &&\n+\trm testfile &&\n+\tmkdir testfile &&\n+\t>testfile/file &&\n+\ttest_must_fail git stash save \"recover regular file\" &&\n+\ttest -f testfile/file &&\n+\n+\tgit add testfile/file &&\n+\ttest_must_fail git stash save \"recover regular file after adding\" &&\n+\ttest -f testfile/file\n+'\n+\n+test_expect_success 'stash a change to turn a non-directory to a directory (forced)' '\n+\tgit stash save --force \"recover regular file (forced)\" &&\n+\t! test -f testfile/file &&\n+\ttest -f testfile\n+'\n+\n test_done\n-- \n1.8.4-rc3-236-g903ae4b\n"}]}