# [PATCH 0/3] Fix up some name hashing uglies.. 4 messages from 2008-02-23 to 2008-02-23. Participants: Linus Torvalds. Thread: https://gitlist.dev/t/12267 ## Linus Torvalds, 2008-02-23 04:32 Subject: [PATCH 0/3] Fix up some name hashing uglies.. Message-ID: URL: https://gitlist.dev/e/alpine.LFD.1.00.0802222029180.21332%40woody.linux-foundation.org ``` I'll follow this with a series of three patches that do the name hashing cleanups I already sent out earlier, but it's now a nice sequence of three independent issues, where each patch is hopefully small and trivial enough that people say "yeah, that's obviously correct. They're individually been run through the test-suite, although the problems that they address are obviously not triggered by any current test, largely because almost nothing actually uses the name hash lookup at all (and the thing that *does* use it - namely "git status", doesn't use it in a way that can actually trigger the bugs afaik). But still, it's best to have it fixed, so that if anybody builds on top of it, they don't get bitten by the issues.. Linus ``` ## Linus Torvalds, 2008-02-23 04:37 Subject: [PATCH] Fix name re-hashing semantics Message-ID: URL: https://gitlist.dev/e/alpine.LFD.1.00.0802222033570.21332%40woody.linux-foundation.org In-Reply-To: ``` From: Linus Torvalds We handled the case of removing and re-inserting cache entries badly, which is something that merging commonly needs to do (removing the different stages, and then re-inserting one of them as the merged state). We even had a rather ugly special case for this failure case, where replace_index_entry() basically turned itself into a no-op if the new and the old entries were the same, exactly because the hash routines didn't handle it on their own. So what this patch does is to not just have the UNHASHED bit, but a HASHED bit too, and when you insert an entry into the name hash, that involves: - clear the UNHASHED bit, because now it's valid again for lookup (which is really all that UNHASHED meant) - if we're being lazy, we're done here (but we still want to clear the UNHASHED bit regardless of lazy mode, since we can become unlazy later, and so we need the UNHASHED bit to always be set correctly, even if we never actually insert the entry into the hash list) - if it was already hashed, we just leave it on the list - otherwise mark it HASHED and insert it into the list this all means that unhashing and rehashing a name all just works automatically. Obviously, you cannot change the name of an entry (that would be a serious bug), but nothing can validly do that anyway (you'd have to allocate a new struct cache_entry anyway since the name length could change), so that's not a new limitation. The code actually gets simpler in many ways, although the lazy hashing does mean that there are a few odd cases (ie something can be marked unhashed even though it was never on the hash in the first place, and isn't actually marked hashed!). Signed-off-by: Linus Torvalds --- This does fix a bug, in the sense that a two- or three-way merge would mark an index entry as being CE_UNHASHED, but then when it got re-inserted it would stay marked as such, so "index_name_exists()" wouldn't find it even though it now exists in the index again. But nobody used it that way, so I guess it didn't matter. Still, this is clearer and works more sanely. cache.h | 4 +++- read-cache.c | 14 +++++++++----- 2 files changed, 12 insertions(+), 6 deletions(-) diff --git a/cache.h b/cache.h index e1000bc..0b69c92 100644 --- a/cache.h +++ b/cache.h @@ -133,7 +133,9 @@ struct cache_entry { #define CE_UPDATE (0x10000) #define CE_REMOVE (0x20000) #define CE_UPTODATE (0x40000) -#define CE_UNHASHED (0x80000) + +#define CE_HASHED (0x100000) +#define CE_UNHASHED (0x200000) static inline unsigned create_ce_flags(size_t len, unsigned stage) { diff --git a/read-cache.c b/read-cache.c index e45f4b3..eb58b03 100644 --- a/read-cache.c +++ b/read-cache.c @@ -37,8 +37,13 @@ static unsigned int hash_name(const char *name, int namelen) static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) { void **pos; - unsigned int hash = hash_name(ce->name, ce_namelen(ce)); + unsigned int hash; + if (ce->ce_flags & CE_HASHED) + return; + ce->ce_flags |= CE_HASHED; + ce->next = NULL; + hash = hash_name(ce->name, ce_namelen(ce)); pos = insert_hash(hash, ce, &istate->name_hash); if (pos) { ce->next = *pos; @@ -59,6 +64,7 @@ static void lazy_init_name_hash(struct index_state *istate) static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce) { + ce->ce_flags &= ~CE_UNHASHED; istate->cache[nr] = ce; if (istate->name_hash_initialized) hash_index_entry(istate, ce); @@ -82,10 +88,8 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache { struct cache_entry *old = istate->cache[nr]; - if (ce != old) { - remove_hash_entry(istate, old); - set_index_entry(istate, nr, ce); - } + remove_hash_entry(istate, old); + set_index_entry(istate, nr, ce); istate->cache_changed = 1; } ``` ## Linus Torvalds, 2008-02-23 04:39 Subject: [PATCH 2/3] Name hash fixups: export (and rename) remove_hash_entry Message-ID: URL: https://gitlist.dev/e/alpine.LFD.1.00.0802222037560.21332%40woody.linux-foundation.org In-Reply-To: ``` From: Linus Torvalds This makes the name hash removal function (which really just sets the bit that disables lookups of it) available to external routines, and makes read_cache_unmerged() use it when it drops an unmerged entry from the index. It's renamed to remove_index_entry(), and we drop the (unused) 'istate' argument. Signed-off-by: Linus Torvalds --- Oops, I forgot to number the previous patch. That was 1/3. The changelog above matches what the patch obviously does. builtin-read-tree.c | 1 + cache.h | 14 ++++++++++++++ read-cache.c | 18 ++---------------- 3 files changed, 17 insertions(+), 16 deletions(-) diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 726fb0b..7bdc312 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -41,6 +41,7 @@ static int read_cache_unmerged(void) for (i = 0; i < active_nr; i++) { struct cache_entry *ce = active_cache[i]; if (ce_stage(ce)) { + remove_index_entry(ce); if (last && !strcmp(ce->name, last->name)) continue; cache_tree_invalidate_path(active_cache_tree, ce->name); diff --git a/cache.h b/cache.h index 0b69c92..88d3b92 100644 --- a/cache.h +++ b/cache.h @@ -137,6 +137,20 @@ struct cache_entry { #define CE_HASHED (0x100000) #define CE_UNHASHED (0x200000) +/* + * We don't actually *remove* it, we can just mark it invalid so that + * we won't find it in lookups. + * + * Not only would we have to search the lists (simple enough), but + * we'd also have to rehash other hash buckets in case this makes the + * hash bucket empty (common). So it's much better to just mark + * it. + */ +static inline void remove_index_entry(struct cache_entry *ce) +{ + ce->ce_flags |= CE_UNHASHED; +} + static inline unsigned create_ce_flags(size_t len, unsigned stage) { if (len >= CE_NAMEMASK) diff --git a/read-cache.c b/read-cache.c index eb58b03..fee0c80 100644 --- a/read-cache.c +++ b/read-cache.c @@ -70,25 +70,11 @@ static void set_index_entry(struct index_state *istate, int nr, struct cache_ent hash_index_entry(istate, ce); } -/* - * We don't actually *remove* it, we can just mark it invalid so that - * we won't find it in lookups. - * - * Not only would we have to search the lists (simple enough), but - * we'd also have to rehash other hash buckets in case this makes the - * hash bucket empty (common). So it's much better to just mark - * it. - */ -static void remove_hash_entry(struct index_state *istate, struct cache_entry *ce) -{ - ce->ce_flags |= CE_UNHASHED; -} - static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce) { struct cache_entry *old = istate->cache[nr]; - remove_hash_entry(istate, old); + remove_index_entry(old); set_index_entry(istate, nr, ce); istate->cache_changed = 1; } @@ -417,7 +403,7 @@ int remove_index_entry_at(struct index_state *istate, int pos) { struct cache_entry *ce = istate->cache[pos]; - remove_hash_entry(istate, ce); + remove_index_entry(ce); istate->cache_changed = 1; istate->cache_nr--; if (pos >= istate->cache_nr) ``` ## Linus Torvalds, 2008-02-23 04:41 Subject: [PATCH 3/3] Use helper function for copying index entry information Message-ID: URL: https://gitlist.dev/e/alpine.LFD.1.00.0802222039250.21332%40woody.linux-foundation.org In-Reply-To: ``` From: Linus Torvalds We used to just memcpy() the index entry when we copied the stat() and SHA1 hash information, which worked well enough back when the index entry was just an exact bit-for-bit representation of the information on disk. However, these days we actually have various management information in the cache entry too, and we should be careful to not overwrite it when we copy the stat information from another index entry. Signed-off-by: Linus Torvalds --- It's still not the prettiest function ever, but I think it's obvious enough what it does. And the call-site is prettier. cache.h | 18 +++++++++++++++++- unpack-trees.c | 2 +- 2 files changed, 18 insertions(+), 2 deletions(-) diff --git a/cache.h b/cache.h index 88d3b92..fa5a9e5 100644 --- a/cache.h +++ b/cache.h @@ -110,7 +110,6 @@ struct ondisk_cache_entry { }; struct cache_entry { - struct cache_entry *next; unsigned int ce_ctime; unsigned int ce_mtime; unsigned int ce_dev; @@ -121,6 +120,7 @@ struct cache_entry { unsigned int ce_size; unsigned int ce_flags; unsigned char sha1[20]; + struct cache_entry *next; char name[FLEX_ARRAY]; /* more */ }; @@ -138,6 +138,22 @@ struct cache_entry { #define CE_UNHASHED (0x200000) /* + * Copy the sha1 and stat state of a cache entry from one to + * another. But we never change the name, or the hash state! + */ +#define CE_STATE_MASK (CE_HASHED | CE_UNHASHED) +static inline void copy_cache_entry(struct cache_entry *dst, struct cache_entry *src) +{ + unsigned int state = dst->ce_flags & CE_STATE_MASK; + + /* Don't copy hash chain and name */ + memcpy(dst, src, offsetof(struct cache_entry, next)); + + /* Restore the hash state */ + dst->ce_flags = (dst->ce_flags & ~CE_STATE_MASK) | state; +} + +/* * We don't actually *remove* it, we can just mark it invalid so that * we won't find it in lookups. * diff --git a/unpack-trees.c b/unpack-trees.c index ec558f9..07c4c28 100644 --- a/unpack-trees.c +++ b/unpack-trees.c @@ -590,7 +590,7 @@ static int merged_entry(struct cache_entry *merge, struct cache_entry *old, * a match. */ if (same(old, merge)) { - memcpy(merge, old, offsetof(struct cache_entry, name)); + copy_cache_entry(merge, old); } else { verify_uptodate(old, o); invalidate_ce_path(old); ```