{"thread":{"id":"12267","subject":"[PATCH 0/3] Fix up some name hashing uglies..","startedAt":"2008-02-23T04:32:59Z","lastAt":"2008-02-23T04:41:17Z","messageCount":4,"participants":["Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"69651","messageId":"alpine.LFD.1.00.0802222029180.21332@woody.linux-foundation.org","threadId":"12267","inReplyTo":null,"subject":"[PATCH 0/3] Fix up some name hashing uglies..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-23T04:32:59Z","receivedAt":"2008-02-23T04:32:59Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nI'll follow this with a series of three patches that do the name hashing \ncleanups I already sent out earlier, but it's now a nice sequence of three \nindependent issues, where each patch is hopefully small and trivial enough \nthat people say \"yeah, that's obviously correct.\n\nThey're individually been run through the test-suite, although the \nproblems that they address are obviously not triggered by any current \ntest, largely because almost nothing actually uses the name hash lookup at \nall (and the thing that *does* use it - namely \"git status\", doesn't use \nit in a way that can actually trigger the bugs afaik).\n\nBut still, it's best to have it fixed, so that if anybody builds on top of \nit, they don't get bitten by the issues..\n\n\t\tLinus\n"},{"id":"69653","messageId":"alpine.LFD.1.00.0802222033570.21332@woody.linux-foundation.org","threadId":"12267","inReplyTo":"alpine.LFD.1.00.0802222029180.21332@woody.linux-foundation.org","subject":"[PATCH] Fix name re-hashing semantics","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-23T04:37:40Z","receivedAt":"2008-02-23T04:37:40Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\n\nWe handled the case of removing and re-inserting cache entries badly,\nwhich is something that merging commonly needs to do (removing the\ndifferent stages, and then re-inserting one of them as the merged\nstate).\n\nWe even had a rather ugly special case for this failure case, where\nreplace_index_entry() basically turned itself into a no-op if the new\nand the old entries were the same, exactly because the hash routines\ndidn't handle it on their own.\n\nSo what this patch does is to not just have the UNHASHED bit, but a\nHASHED bit too, and when you insert an entry into the name hash, that\ninvolves:\n\n - clear the UNHASHED bit, because now it's valid again for lookup\n   (which is really all that UNHASHED meant)\n\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\n   later, and so we need the UNHASHED bit to always be set correctly,\n   even if we never actually insert the entry into the hash list)\n\n - if it was already hashed, we just leave it on the list\n\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\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis does fix a bug, in the sense that a two- or three-way merge would \nmark an index entry as being CE_UNHASHED, but then when it got re-inserted \nit would stay marked as such, so \"index_name_exists()\" wouldn't find it \neven though it now exists in the index again.\n\nBut nobody used it that way, so I guess it didn't matter. Still, this is \nclearer and works more sanely.\n\n cache.h      |    4 +++-\n read-cache.c |   14 +++++++++-----\n 2 files changed, 12 insertions(+), 6 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e1000bc..0b69c92 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -133,7 +133,9 @@ 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 static inline unsigned create_ce_flags(size_t len, unsigned stage)\n {\ndiff --git a/read-cache.c b/read-cache.c\nindex e45f4b3..eb58b03 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,6 +64,7 @@ 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@@ -82,10 +88,8 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache\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_hash_entry(istate, old);\n+\tset_index_entry(istate, nr, ce);\n \tistate->cache_changed = 1;\n }\n \n"},{"id":"69654","messageId":"alpine.LFD.1.00.0802222037560.21332@woody.linux-foundation.org","threadId":"12267","inReplyTo":"alpine.LFD.1.00.0802222033570.21332@woody.linux-foundation.org","subject":"[PATCH 2/3] Name hash fixups: export (and rename) remove_hash_entry","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-23T04:39:21Z","receivedAt":"2008-02-23T04:39:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\n\nThis makes the name hash removal function (which really just sets the\nbit that disables lookups of it) available to external routines, and\nmakes read_cache_unmerged() use it when it drops an unmerged entry from\nthe index.\n\nIt's renamed to remove_index_entry(), and we drop the (unused) 'istate'\nargument.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nOops, I forgot to number the previous patch. That was 1/3.\n\nThe changelog above matches what the patch obviously does.\n\n builtin-read-tree.c |    1 +\n cache.h             |   14 ++++++++++++++\n read-cache.c        |   18 ++----------------\n 3 files changed, 17 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex 726fb0b..7bdc312 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -41,6 +41,7 @@ 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);\ndiff --git a/cache.h b/cache.h\nindex 0b69c92..88d3b92 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -137,6 +137,20 @@ struct cache_entry {\n #define CE_HASHED    (0x100000)\n #define CE_UNHASHED  (0x200000)\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 eb58b03..fee0c80 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -70,25 +70,11 @@ 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-\tremove_hash_entry(istate, old);\n+\tremove_index_entry(old);\n \tset_index_entry(istate, nr, ce);\n \tistate->cache_changed = 1;\n }\n@@ -417,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)\n"},{"id":"69655","messageId":"alpine.LFD.1.00.0802222039250.21332@woody.linux-foundation.org","threadId":"12267","inReplyTo":"alpine.LFD.1.00.0802222037560.21332@woody.linux-foundation.org","subject":"[PATCH 3/3] Use helper function for copying index entry information","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-02-23T04:41:17Z","receivedAt":"2008-02-23T04:41:17Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\n\nWe used to just memcpy() the index entry when we copied the stat() and\nSHA1 hash information, which worked well enough back when the index\nentry was just an exact bit-for-bit representation of the information on\ndisk.\n\nHowever, these days we actually have various management information in\nthe cache entry too, and we should be careful to not overwrite it when\nwe copy the stat information from another index entry.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\nIt's still not the prettiest function ever, but I think it's obvious \nenough what it does. And the call-site is prettier.\n\n cache.h        |   18 +++++++++++++++++-\n unpack-trees.c |    2 +-\n 2 files changed, 18 insertions(+), 2 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 88d3b92..fa5a9e5 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -110,7 +110,6 @@ struct ondisk_cache_entry {\n };\n \n struct cache_entry {\n-\tstruct cache_entry *next;\n \tunsigned int ce_ctime;\n \tunsigned int ce_mtime;\n \tunsigned int ce_dev;\n@@ -121,6 +120,7 @@ struct cache_entry {\n \tunsigned int ce_size;\n \tunsigned int ce_flags;\n \tunsigned char sha1[20];\n+\tstruct cache_entry *next;\n \tchar name[FLEX_ARRAY]; /* more */\n };\n \n@@ -138,6 +138,22 @@ struct cache_entry {\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+\tunsigned int state = dst->ce_flags & CE_STATE_MASK;\n+\n+\t/* Don't copy hash chain and name */\n+\tmemcpy(dst, src, offsetof(struct cache_entry, next));\n+\n+\t/* Restore the hash state */\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  *\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"}]}