{"thread":{"id":"12237","subject":"[RFH] CE_REMOVE conversion","startedAt":"2008-02-21T08:39:28Z","lastAt":"2008-02-21T20:08:18Z","messageCount":10,"participants":["Junio C Hamano","Linus Torvalds","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"69465","messageId":"7v7igywvnj.fsf@gitster.siamese.dyndns.org","threadId":"12237","inReplyTo":null,"subject":"[RFH] CE_REMOVE conversion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-21T08:39:28Z","receivedAt":"2008-02-21T08:39:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"You converted \"ce->ce_mode = 0\" to \"ce->ce_flags |= CE_REMOVE\" in an\nearlier commit 7a51ed6 (Make on-disk index representation\nseparate from in-core one).\n\nI am having two issues with this conversion, related to read-tree.\n\nIf you say \"git reset --hard\" with an unmerged path in the\nindex, the entry does not get resurrected from the HEAD.  It\ninstead just goes away (i.e. you lose a path in the index).\nIf you run \"git reset --hard\" twice, the second run will\nresurrect it, of course, as the first one removed the unmerged\npaths.\n\n\"git reset --hard\" internally runs \"read-tree -u --reset HEAD\",\nand the oneway_merge() misbehaves.\n\n        commit 7a51ed66f653c248993b3c4a61932e47933d835e\n        Author: Linus Torvalds <torvalds@linux-foundation.org>\n        Date:   Mon Jan 14 16:03:17 2008 -0800\n\n            Make on-disk index representation separate from in-core one\n\n        diff --git a/builtin-read-tree.c b/builtin-read-tree.c\n        index c0ea034..5785401 100644\n        --- a/builtin-read-tree.c\n        +++ b/builtin-read-tree.c\n        @@ -45,8 +45,7 @@ static int read_cache_unmerged(void)\n                                        continue;\n                                cache_tree_invalidate_path(active_cache_tree, ce->name);\n                                last = ce;\n        -\t\t\tce->ce_mode = 0;\n        -\t\t\tce->ce_flags &= ~htons(CE_STAGEMASK);\n        +\t\t\tce->ce_flags |= CE_REMOVE;\n                        }\n                        *dst++ = ce;\n                }\n\nOne issue is somewhat apparent.  The conversion forgot to drop\nthe stage information (i.e. it does not tell \"that stage#0 path\nis to be removed\" anymore).\n\nAnother thing is a bit trickier.  Now because you do not smudge\nce->ce_mode, when oneway_merge in unpack-trees.c compares it\n(which comes as *old) with what is read from HEAD, it triggers\nthis codepath:\n\n\tif (old && same(old, a)) {\n\t\tif (o->reset) {\n\t\t\tstruct stat st;\n\t\t\tif (lstat(old->name, &st) ||\n\t\t\t    ce_match_stat(old, &st, CE_MATCH_IGNORE_VALID))\n\t\t\t\told->ce_flags |= CE_UPDATE;\n\t\t}\n\t\treturn keep_entry(old, o);\n\t}\n\nHere, same(old, a) yields true, old->ce_flags gets CE_UPDATE,\nand then keep_entry(old, o) keeps that old entry, which is at\nstage #1 and has (CE_REMOVE|CE_UPDATE) flags set.  This index is\nwritten out, making the resulting index empty.\n\nThe reason we keep an index entry with ce_mode = 0 (and now\nCE_REMOVE) when we want to remive it is because we would want to\nbe able to say \"propagate this change to the work tree\" when run\nwith CE_UPDATE.  But I think the reason read_cache_unmerged()\nsays \"this unmerged entry is gone\" is _not_ because we would\nwant to remove the corresponding path from the work tree.\n\nThe old code happened to work because \"ce_mode = 0\" entries\nwould have never matched with what was read from the HEAD tree,\nand we would never have triggered the keep_entry() codepath.\n\nWe could of course hack read_cache_unmerged() to:\n\n\tif (ce_stage(ce)) {\n\t\tif (last && !strcmp(ce->name, last->name))\n\t\t\tcontinue;\n\t\tcache_tree_invalidate_path(active_cache_tree, ce->name);\n\t\tlast = ce;\n\t\tce->ce_flags &= ~CE_STAGEMASK;\n\t\t/* Do not match with entries from trees! */\n\t\tce->ce_mode = 0;\n\t}\n\t*dst++ = ce;\n\nbut I am wondering if we should instead really _remove_ entries\nfrom the index instead, just like the attached patch.\n\nThoughts?\n\n builtin-read-tree.c |    2 +-\n t/t7104-reset.sh    |   35 +++++++++++++++++++++++++++++++++++\n 2 files changed, 36 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex 5785401..726fb0b 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -45,7 +45,7 @@ static int read_cache_unmerged(void)\n \t\t\t\tcontinue;\n \t\t\tcache_tree_invalidate_path(active_cache_tree, ce->name);\n \t\t\tlast = ce;\n-\t\t\tce->ce_flags |= CE_REMOVE;\n+\t\t\tcontinue;\n \t\t}\n \t\t*dst++ = ce;\n \t}\ndiff --git a/t/t7104-reset.sh b/t/t7104-reset.sh\nnew file mode 100755\nindex 0000000..831078c\n--- /dev/null\n+++ b/t/t7104-reset.sh\n@@ -0,0 +1,35 @@\n+#!/bin/sh\n+\n+test_description='reset --hard unmerged'\n+\n+. ./test-lib.sh\n+\n+test_expect_success setup '\n+\n+\t>hello &&\n+\tgit add hello &&\n+\tgit commit -m world &&\n+\n+\tH=$(git rev-parse :hello) &&\n+\tgit rm --cached hello &&\n+\tfor i in 1 2 3\n+\tdo\n+\t\techo \"100644 $H $i\thello\"\n+\tdone | git update-index --index-info &&\n+\n+\trm -f hello &&\n+\tmkdir -p hello &&\n+\t>hello/world &&\n+\ttest \"$(git ls-files -o)\" = hello/world\n+\n+'\n+\n+test_expect_failure 'reset --hard loses the index' '\n+\n+\tgit reset --hard &&\n+\tgit ls-files --error-unmatch hello &&\n+\ttest -f hello\n+\n+'\n+\n+test_done\n"},{"id":"69466","messageId":"7vy79evfsn.fsf@gitster.siamese.dyndns.org","threadId":"12237","inReplyTo":"7v7igywvnj.fsf@gitster.siamese.dyndns.org","subject":"[RFH] index_name_exists() conversion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-21T09:07:20Z","receivedAt":"2008-02-21T09:07:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"While (hopefully) I have your attention, I have another question\nabout the recent optimization.\n\n        commit cf558704fb68514a820e3666968967c900e0fd29\n        Author: Linus Torvalds <torvalds@linux-foundation.org>\n\n            Create pathname-based hash-table lookup into index\n\n        diff --git a/dir.c b/dir.c\n        index 1b9cc7a..6543105 100644\n        --- a/dir.c\n        +++ b/dir.c\n        @@ -346,7 +346,7 @@ static struct dir_entry *dir_entry_new(cons...\n\n         struct dir_entry *dir_add_name(struct dir_struct *dir, const c...\n         {\n        -\tif (cache_name_pos(pathname, len) >= 0)\n        +\tif (cache_name_exists(pathname, len))\n                        return NULL;\n\n                ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);\n\nThis used to check if there is a stage#0 entry of that name in\nthe index.  But the name-hash based index look-up does not care\nabout the stage as far as I can tell.\n\nI haven't managed to come up with a failure case to demonstrate,\nbut I think this can affect ls-files and clean, potentially in a\nbad way.  \"git add dir/\" to resolve unmerged paths under dir/\nsomewhere should not be affected, as the codepath calls\nread_directory() before reading the cache (so the check will\nalways say \"Nope, we do not have such a path in the index yet\").\n\nI am not sure what the right solution would be.  The motivation\nfor the patch was to make \"does this name exist in the index\"\nand also \"does this exist under an equivalent name\" efficient,\nbut it is asking a question that is not precise enough.  Are we\ninterested in such an entry at any stage, or only at stage#0, or\nwhat?\n\nThis could be related to the recent \"status segfaults, bisected\nto cf558704\" issue posted to the list.  I dunno.\n"},{"id":"69482","messageId":"alpine.LFD.1.00.0802210746410.7833@woody.linux-foundation.org","threadId":"12237","inReplyTo":"7v7igywvnj.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFH] CE_REMOVE conversion","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-21T16:05:42Z","receivedAt":"2008-02-21T16:05:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Feb 2008, Junio C Hamano wrote:\n> \n> but I am wondering if we should instead really _remove_ entries\n> from the index instead, just like the attached patch.\n\nAbsolutely. I think that your patch is \"ObviouslyCorrect(tm)\", and that \ncode should never have used CE_REMOVE in the first place. The fact that \nthe old code worked was perhaps intentional, but still very subtle and \nlucky.\n\nThe whole (and only) point of CE_REMOVE was and is to do the \"-u\" handling \nwhen resolving a merge, and keep the thing in the index in order to later \nstill do work with it (ie remove it) when we have verified that the index \nis complete. But that's not what \"read_cache_unmerged()\" is about: it's \nvery explicitly documented to just ignore the unmerged entries.\n\nSo your patch looks very good to me. Basically, the merge code absolutely \ndoes not want to be called with some entries already marked as CE_REMOVE \n(it's supposed to *add* those markers as part of resolving the merge, but \nit is not able to handle them in the source).\n\nSo ack, ack, ack.\n\n\n\t\t\tLinus\n"},{"id":"69484","messageId":"alpine.LFD.1.00.0802210806540.7833@woody.linux-foundation.org","threadId":"12237","inReplyTo":"7vy79evfsn.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFH] index_name_exists() conversion","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-21T16:15:22Z","receivedAt":"2008-02-21T16:15:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Feb 2008, Junio C Hamano wrote:\n>\n>          struct dir_entry *dir_add_name(struct dir_struct *dir, const c...\n>          {\n>         -\tif (cache_name_pos(pathname, len) >= 0)\n>         +\tif (cache_name_exists(pathname, len))\n>                         return NULL;\n> \n>                 ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);\n> \n> This used to check if there is a stage#0 entry of that name in\n> the index.  But the name-hash based index look-up does not care\n> about the stage as far as I can tell.\n\nI think the new code is much more correct, and we should always care about \nwhether the name exists in the index, not whether it exists in stage#0.\n\nIOW, if we ask for \"show other files\", we definitely want to ignore \npaths we already know about, and conversely, if we do an operation that is \nsupposed to care about files in a directory we already know about, then an \nunmerged entry should count the same as a merged one.\n\n> This could be related to the recent \"status segfaults, bisected\n> to cf558704\" issue posted to the list.  I dunno.\n\nIs there a backtrace for that? It's certainly possible that some strange \npath depended on only matching merged entries, but I would consider that \nunlikely and buggy.\n\nThe segfault is more likely related to something more subtle, like \nactually freeing a \"cache_entry\" after having removed it from the index \n(which we should never do - they were always supposed to stay around \nbecause they might not have been allocated with 'malloc()' in the first \nplace, but with the name indexing thing it now is *always* a bug to do it, \neven if you _did_ allocate it with free()).\n\n(Also, some code used to just reuse the same cache entry multiple times, \nand that got illegal for the same reason).\n\n\t\tLinus\n"},{"id":"69486","messageId":"alpine.LSU.1.00.0802211629070.17164@racer.site","threadId":"12237","inReplyTo":"alpine.LFD.1.00.0802210806540.7833@woody.linux-foundation.org","subject":"Re: [RFH] index_name_exists() conversion","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-02-21T16:29:46Z","receivedAt":"2008-02-21T16:29:46Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 21 Feb 2008, Linus Torvalds wrote:\n\n> I think the new code is much more correct,\n\nHeh.  So much truthiness in this half-sentence ;-)\n\nCiao,\nDscho\n"},{"id":"69488","messageId":"7vodaauunn.fsf@gitster.siamese.dyndns.org","threadId":"12237","inReplyTo":"alpine.LFD.1.00.0802210746410.7833@woody.linux-foundation.org","subject":"Re: [RFH] CE_REMOVE conversion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-21T16:43:56Z","receivedAt":"2008-02-21T16:43:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Thu, 21 Feb 2008, Junio C Hamano wrote:\n>> \n>> but I am wondering if we should instead really _remove_ entries\n>> from the index instead, just like the attached patch.\n> ...\n> So your patch looks very good to me. Basically, the merge code absolutely \n> does not want to be called with some entries already marked as CE_REMOVE \n> (it's supposed to *add* those markers as part of resolving the merge, but \n> it is not able to handle them in the source).\n>\n> So ack, ack, ack.\n\nAnd we probably should unhash the entry instead of just removing\nit?  Come to think of it, I am starting to wonder if the\nentries unpack-trees add to and drop from the index are hashed\nand unhashed correctly...\n"},{"id":"69492","messageId":"alpine.LFD.1.00.0802210816380.7833@woody.linux-foundation.org","threadId":"12237","inReplyTo":"alpine.LFD.1.00.0802210806540.7833@woody.linux-foundation.org","subject":"Re: [RFH] index_name_exists() conversion","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-21T17:00:55Z","receivedAt":"2008-02-21T17:00:55Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Feb 2008, Linus Torvalds wrote:\n> \n> (Also, some code used to just reuse the same cache entry multiple times, \n> and that got illegal for the same reason).\n\nAhh. I think I may have found it.\n\nIt's stupid.\n\nIn hash_index_entry(), we insert the entry into the name hash, but if it \ngot inserted as the first entry, we don't actually set the ->next pointer \nto NULL.\n\nSo the chain would end up pointing to some random crud. I think we were \njust lucky with our allocators generally filling those things with zero.\n\nSee if this fixes it.\n\n\t\tLinus\n\n---\ndiff --git a/read-cache.c b/read-cache.c\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -39,6 +39,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \tvoid **pos;\n \tunsigned int hash = hash_name(ce->name, ce_namelen(ce));\n \n+\tce->next = NULL;\n \tpos = insert_hash(hash, ce, &istate->name_hash);\n \tif (pos) {\n \t\tce->next = *pos;\n"},{"id":"69496","messageId":"alpine.LFD.1.00.0802210922100.7833@woody.linux-foundation.org","threadId":"12237","inReplyTo":"7vodaauunn.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFH] CE_REMOVE conversion","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-21T17:31:05Z","receivedAt":"2008-02-21T17:31:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Feb 2008, Junio C Hamano wrote:\n> \n> And we probably should unhash the entry instead of just removing\n> it?  Come to think of it, I am starting to wonder if the\n> entries unpack-trees add to and drop from the index are hashed\n> and unhashed correctly...\n\nHeh. This was exactly what I was working on, and here's an early patch.\n\nI say \"early\" just because I haven't really gone through it more than \nonce, and testing that it passes all the tests.\n\nIt includes your \"continue\" fix, since that was actually related to the \n\"remove_index_entry()\" addition this needs. It also contains the hash next \npointer initialization.\n\nThe bulk of the patch is moving (and renaming) the \"remove_index_entry()\" \nfunction (used to be remove_hash_entry, but it's very specific to the \nindex, not to general hashes), and the comment that goes with it.\n\nI also made that \"copy a cache entry\" thing use a function of its own, and \nmade sure it saves/restores the hash pointer rather than using a naked \n\"memcpy()\" with offsetof etc. At least it's abstracted away, even if the \nfunction itself is ugly as sin.\n\nEverything else is really just one-liners.\n\nBut I'm still looking at this. In particular, I want to add some \nassertions to make sure the index state matches the name hash state, but \nyour lazy patch makes that less convenient.\n\n\t\tLinus\n\n---\n builtin-read-tree.c |    3 ++-\n cache.h             |   21 +++++++++++++++++++++\n read-cache.c        |   19 +++----------------\n unpack-trees.c      |    2 +-\n 4 files changed, 27 insertions(+), 18 deletions(-)\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex 5785401..7bdc312 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -41,11 +41,12 @@ static int read_cache_unmerged(void)\n \tfor (i = 0; i < active_nr; i++) {\n \t\tstruct cache_entry *ce = active_cache[i];\n \t\tif (ce_stage(ce)) {\n+\t\t\tremove_index_entry(ce);\n \t\t\tif (last && !strcmp(ce->name, last->name))\n \t\t\t\tcontinue;\n \t\t\tcache_tree_invalidate_path(active_cache_tree, ce->name);\n \t\t\tlast = ce;\n-\t\t\tce->ce_flags |= CE_REMOVE;\n+\t\t\tcontinue;\n \t\t}\n \t\t*dst++ = ce;\n \t}\ndiff --git a/cache.h b/cache.h\nindex e1000bc..32fa6da 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -135,6 +135,27 @@ struct cache_entry {\n #define CE_UPTODATE  (0x40000)\n #define CE_UNHASHED  (0x80000)\n \n+static inline void copy_cache_entry(struct cache_entry *dst, struct cache_entry *src)\n+{\n+\tstruct cache_entry *next = dst->next;\n+\tmemcpy(dst, src, offsetof(struct cache_entry, name));\n+\tdst->next = next;\n+}\n+\n+/*\n+ * We don't actually *remove* it, we can just mark it invalid so that\n+ * we won't find it in lookups.\n+ *\n+ * Not only would we have to search the lists (simple enough), but\n+ * we'd also have to rehash other hash buckets in case this makes the\n+ * hash bucket empty (common). So it's much better to just mark\n+ * it.\n+ */\n+static inline void remove_index_entry(struct cache_entry *ce)\n+{\n+\tce->ce_flags |= CE_UNHASHED;\n+}\n+\n static inline unsigned create_ce_flags(size_t len, unsigned stage)\n {\n \tif (len >= CE_NAMEMASK)\ndiff --git a/read-cache.c b/read-cache.c\nindex e45f4b3..e8e2be8 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -39,6 +39,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \tvoid **pos;\n \tunsigned int hash = hash_name(ce->name, ce_namelen(ce));\n \n+\tce->next = NULL;\n \tpos = insert_hash(hash, ce, &istate->name_hash);\n \tif (pos) {\n \t\tce->next = *pos;\n@@ -64,26 +65,12 @@ static void set_index_entry(struct index_state *istate, int nr, struct cache_ent\n \t\thash_index_entry(istate, ce);\n }\n \n-/*\n- * We don't actually *remove* it, we can just mark it invalid so that\n- * we won't find it in lookups.\n- *\n- * Not only would we have to search the lists (simple enough), but\n- * we'd also have to rehash other hash buckets in case this makes the\n- * hash bucket empty (common). So it's much better to just mark\n- * it.\n- */\n-static void remove_hash_entry(struct index_state *istate, struct cache_entry *ce)\n-{\n-\tce->ce_flags |= CE_UNHASHED;\n-}\n-\n static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n \tstruct cache_entry *old = istate->cache[nr];\n \n \tif (ce != old) {\n-\t\tremove_hash_entry(istate, old);\n+\t\tremove_index_entry(old);\n \t\tset_index_entry(istate, nr, ce);\n \t}\n \tistate->cache_changed = 1;\n@@ -413,7 +400,7 @@ int remove_index_entry_at(struct index_state *istate, int pos)\n {\n \tstruct cache_entry *ce = istate->cache[pos];\n \n-\tremove_hash_entry(istate, ce);\n+\tremove_index_entry(ce);\n \tistate->cache_changed = 1;\n \tistate->cache_nr--;\n \tif (pos >= istate->cache_nr)\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex ec558f9..07c4c28 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -590,7 +590,7 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old,\n \t\t * a match.\n \t\t */\n \t\tif (same(old, merge)) {\n-\t\t\tmemcpy(merge, old, offsetof(struct cache_entry, name));\n+\t\t\tcopy_cache_entry(merge, old);\n \t\t} else {\n \t\t\tverify_uptodate(old, o);\n \t\t\tinvalidate_ce_path(old);\n"},{"id":"69505","messageId":"alpine.LFD.1.00.0802211157100.19896@woody.linux-foundation.org","threadId":"12237","inReplyTo":"alpine.LFD.1.00.0802210922100.7833@woody.linux-foundation.org","subject":"Re: [RFH] CE_REMOVE conversion","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-21T20:06:20Z","receivedAt":"2008-02-21T20:06:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 21 Feb 2008, Linus Torvalds wrote:\n> \n> I say \"early\" just because I haven't really gone through it more than \n> once, and testing that it passes all the tests.\n\nOk, here's an improved version. This is a bit larger, but having now \nthought the problems through, I think this is *much* better.\n\nThe thing is, we used to not be able to handle the case of removing a \nindex entry and then re-inserting it, and we even had a rather ugly \nspecial case for that reason, where replace_index_entry() basically turned \nitself into a no-op if the new and the old entries were the same.\n\nBut the merging code really wants to remove a set of entries and then \nreplace them with a new one, and that whole logic needed the hash lists to \nbe handled *properly*.\n\nSo what this patch does is to not just have the UNHASHED bit, but a HASHED \nbit too, and when you insert an entry into the name hash, that involves:\n\n - clear the UNHASHED bit, because now it's valid again for lookup (which \n   is really all that UNHASHED meant)\n - if we're being lazy, we're done here (but we still want to clear the \n   UNHASHED bit regardless of lazy mode, since we can become unlazy later, \n   and so we need the UNHASHED bit to always be set correctly, even if we \n   never actually insert the entry into the hash list)\n - if it was already hashed, we just leave it on the list\n - otherwise mark it HASHED and insert it into the list\n\nthis all means that unhashing and rehashing a name all just works \nautomatically. Obviously, you cannot change the name of an entry (that \nwould be a serious bug), but nothing can validly do that anyway (you'd \nhave to allocate a new struct cache_entry anyway since the name length \ncould change), so that's not a new limitation.\n\nThe code actually gets simpler in many ways, although the lazy hashing \ndoes mean that there are a few odd cases (ie something can be marked \nunhashed even though it was never on the hash in the first place, and \nisn't actually marked hashed!).\n\nI haven't actually added any code to verify that the name hash state \nmatches the index state, but I feel pretty good about this patch anyway: \nit passes my \"it makes sense\" filters in ways that the previous one \ndidn't.\n\n\t\tLinus\n\n---\n builtin-read-tree.c |    3 ++-\n cache.h             |   35 ++++++++++++++++++++++++++++++++++-\n read-cache.c        |   30 ++++++++++--------------------\n unpack-trees.c      |    2 +-\n 4 files changed, 47 insertions(+), 23 deletions(-)\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex 5785401..7bdc312 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -41,11 +41,12 @@ static int read_cache_unmerged(void)\n \tfor (i = 0; i < active_nr; i++) {\n \t\tstruct cache_entry *ce = active_cache[i];\n \t\tif (ce_stage(ce)) {\n+\t\t\tremove_index_entry(ce);\n \t\t\tif (last && !strcmp(ce->name, last->name))\n \t\t\t\tcontinue;\n \t\t\tcache_tree_invalidate_path(active_cache_tree, ce->name);\n \t\t\tlast = ce;\n-\t\t\tce->ce_flags |= CE_REMOVE;\n+\t\t\tcontinue;\n \t\t}\n \t\t*dst++ = ce;\n \t}\ndiff --git a/cache.h b/cache.h\nindex e1000bc..0ae33f4 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -133,7 +133,40 @@ struct cache_entry {\n #define CE_UPDATE    (0x10000)\n #define CE_REMOVE    (0x20000)\n #define CE_UPTODATE  (0x40000)\n-#define CE_UNHASHED  (0x80000)\n+\n+#define CE_HASHED    (0x100000)\n+#define CE_UNHASHED  (0x200000)\n+\n+/*\n+ * Copy the sha1 and stat state of a cache entry from one to\n+ * another. But we never change the name, or the hash state!\n+ */\n+#define CE_STATE_MASK (CE_HASHED | CE_UNHASHED)\n+static inline void copy_cache_entry(struct cache_entry *dst, struct cache_entry *src)\n+{\n+\tstruct cache_entry *next = dst->next;\n+\tunsigned int state = dst->ce_flags & CE_STATE_MASK;\n+\n+\tmemcpy(dst, src, offsetof(struct cache_entry, name));\n+\n+\t/* Restore the hash state */\n+\tdst->next = next;\n+\tdst->ce_flags = (dst->ce_flags & ~CE_STATE_MASK) | state;\n+}\n+\n+/*\n+ * We don't actually *remove* it, we can just mark it invalid so that\n+ * we won't find it in lookups.\n+ *\n+ * Not only would we have to search the lists (simple enough), but\n+ * we'd also have to rehash other hash buckets in case this makes the\n+ * hash bucket empty (common). So it's much better to just mark\n+ * it.\n+ */\n+static inline void remove_index_entry(struct cache_entry *ce)\n+{\n+\tce->ce_flags |= CE_UNHASHED;\n+}\n \n static inline unsigned create_ce_flags(size_t len, unsigned stage)\n {\ndiff --git a/read-cache.c b/read-cache.c\nindex e45f4b3..fee0c80 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -37,8 +37,13 @@ static unsigned int hash_name(const char *name, int namelen)\n static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n {\n \tvoid **pos;\n-\tunsigned int hash = hash_name(ce->name, ce_namelen(ce));\n+\tunsigned int hash;\n \n+\tif (ce->ce_flags & CE_HASHED)\n+\t\treturn;\n+\tce->ce_flags |= CE_HASHED;\n+\tce->next = NULL;\n+\thash = hash_name(ce->name, ce_namelen(ce));\n \tpos = insert_hash(hash, ce, &istate->name_hash);\n \tif (pos) {\n \t\tce->next = *pos;\n@@ -59,33 +64,18 @@ static void lazy_init_name_hash(struct index_state *istate)\n \n static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n+\tce->ce_flags &= ~CE_UNHASHED;\n \tistate->cache[nr] = ce;\n \tif (istate->name_hash_initialized)\n \t\thash_index_entry(istate, ce);\n }\n \n-/*\n- * We don't actually *remove* it, we can just mark it invalid so that\n- * we won't find it in lookups.\n- *\n- * Not only would we have to search the lists (simple enough), but\n- * we'd also have to rehash other hash buckets in case this makes the\n- * hash bucket empty (common). So it's much better to just mark\n- * it.\n- */\n-static void remove_hash_entry(struct index_state *istate, struct cache_entry *ce)\n-{\n-\tce->ce_flags |= CE_UNHASHED;\n-}\n-\n static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n \tstruct cache_entry *old = istate->cache[nr];\n \n-\tif (ce != old) {\n-\t\tremove_hash_entry(istate, old);\n-\t\tset_index_entry(istate, nr, ce);\n-\t}\n+\tremove_index_entry(old);\n+\tset_index_entry(istate, nr, ce);\n \tistate->cache_changed = 1;\n }\n \n@@ -413,7 +403,7 @@ int remove_index_entry_at(struct index_state *istate, int pos)\n {\n \tstruct cache_entry *ce = istate->cache[pos];\n \n-\tremove_hash_entry(istate, ce);\n+\tremove_index_entry(ce);\n \tistate->cache_changed = 1;\n \tistate->cache_nr--;\n \tif (pos >= istate->cache_nr)\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex ec558f9..07c4c28 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -590,7 +590,7 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old,\n \t\t * a match.\n \t\t */\n \t\tif (same(old, merge)) {\n-\t\t\tmemcpy(merge, old, offsetof(struct cache_entry, name));\n+\t\t\tcopy_cache_entry(merge, old);\n \t\t} else {\n \t\t\tverify_uptodate(old, o);\n \t\t\tinvalidate_ce_path(old);\n"},{"id":"69506","messageId":"7v1w76ul70.fsf@gitster.siamese.dyndns.org","threadId":"12237","inReplyTo":"alpine.LFD.1.00.0802210922100.7833@woody.linux-foundation.org","subject":"Re: [RFH] CE_REMOVE conversion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-21T20:08:18Z","receivedAt":"2008-02-21T20:08:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> It includes your \"continue\" fix, since that was actually related to the \n> \"remove_index_entry()\" addition this needs. It also contains the hash next \n> pointer initialization.\n\nIn the meantime, 'master' will get that single-liner \"continue\"\nfix, which may conflict but the resolution is trivial.\n\n> But I'm still looking at this. In particular, I want to add some \n> assertions to make sure the index state matches the name hash state, but \n> your lazy patch makes that less convenient.\n\nPlease feel free to revert it.\n"}]}