From 8387ff2577eb9ed245df9a39947f66976c6bcd02 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Fri, 10 Jun 2016 07:51:30 -0700 Subject: vfs: make the string hashes salt the hash We always mixed in the parent pointer into the dentry name hash, but we did it late at lookup time. It turns out that we can simplify that lookup-time action by salting the hash with the parent pointer early instead of late. A few other users of our string hashes also wanted to mix in their own pointers into the hash, and those are updated to use the same mechanism. Hash users that don't have any particular initial salt can just use the NULL pointer as a no-salt. Cc: Vegard Nossum Cc: George Spelvin Cc: Al Viro Signed-off-by: Linus Torvalds --- fs/dcache.c | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-) (limited to 'fs/dcache.c') diff --git a/fs/dcache.c b/fs/dcache.c index 817c243c1ff1..9522b8b63871 100644 --- a/fs/dcache.c +++ b/fs/dcache.c @@ -104,10 +104,8 @@ static unsigned int d_hash_shift __read_mostly; static struct hlist_bl_head *dentry_hashtable __read_mostly; -static inline struct hlist_bl_head *d_hash(const struct dentry *parent, - unsigned int hash) +static inline struct hlist_bl_head *d_hash(unsigned int hash) { - hash += (unsigned long) parent / L1_CACHE_BYTES; return dentry_hashtable + hash_32(hash, d_hash_shift); } @@ -488,7 +486,7 @@ void __d_drop(struct dentry *dentry) if (unlikely(IS_ROOT(dentry))) b = &dentry->d_sb->s_anon; else - b = d_hash(dentry->d_parent, dentry->d_name.hash); + b = d_hash(dentry->d_name.hash); hlist_bl_lock(b); __hlist_bl_del(&dentry->d_hash); @@ -1670,7 +1668,7 @@ struct dentry *d_alloc_name(struct dentry *parent, const char *name) struct qstr q; q.name = name; - q.hash_len = hashlen_string(name); + q.hash_len = hashlen_string(parent, name); return d_alloc(parent, &q); } EXPORT_SYMBOL(d_alloc_name); @@ -2094,7 +2092,7 @@ struct dentry *__d_lookup_rcu(const struct dentry *parent, { u64 hashlen = name->hash_len; const unsigned char *str = name->name; - struct hlist_bl_head *b = d_hash(parent, hashlen_hash(hashlen)); + struct hlist_bl_head *b = d_hash(hashlen_hash(hashlen)); struct hlist_bl_node *node; struct dentry *dentry; @@ -2211,7 +2209,7 @@ struct dentry *__d_lookup(const struct dentry *parent, const struct qstr *name) unsigned int len = name->len; unsigned int hash = name->hash; const unsigned char *str = name->name; - struct hlist_bl_head *b = d_hash(parent, hash); + struct hlist_bl_head *b = d_hash(hash); struct hlist_bl_node *node; struct dentry *found = NULL; struct dentry *dentry; @@ -2291,7 +2289,7 @@ struct dentry *d_hash_and_lookup(struct dentry *dir, struct qstr *name) * calculate the standard hash first, as the d_op->d_hash() * routine may choose to leave the hash value unchanged. */ - name->hash = full_name_hash(name->name, name->len); + name->hash = full_name_hash(dir, name->name, name->len); if (dir->d_flags & DCACHE_OP_HASH) { int err = dir->d_op->d_hash(dir, name); if (unlikely(err < 0)) @@ -2364,7 +2362,7 @@ static void __d_rehash(struct dentry * entry, struct hlist_bl_head *b) static void _d_rehash(struct dentry * entry) { - __d_rehash(entry, d_hash(entry->d_parent, entry->d_name.hash)); + __d_rehash(entry, d_hash(entry->d_name.hash)); } /** @@ -2821,7 +2819,7 @@ static void __d_move(struct dentry *dentry, struct dentry *target, * for the same hash queue because of how unlikely it is. */ __d_drop(dentry); - __d_rehash(dentry, d_hash(target->d_parent, target->d_name.hash)); + __d_rehash(dentry, d_hash(target->d_name.hash)); /* * Unhash the target (d_delete() is not usable here). If exchanging @@ -2829,8 +2827,7 @@ static void __d_move(struct dentry *dentry, struct dentry *target, */ __d_drop(target); if (exchange) { - __d_rehash(target, - d_hash(dentry->d_parent, dentry->d_name.hash)); + __d_rehash(target, d_hash(dentry->d_name.hash)); } /* Switch the names.. */ -- cgit From 703b5faf22fbddf984a361e6555f3a03fdba63d9 Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Fri, 10 Jun 2016 00:22:12 -0400 Subject: fs/dcache.c: Save one 32-bit multiply in dcache lookup Noe that we're mixing in the parent pointer earlier, we don't need to use hash_32() to mix its bits. Instead, we can just take the msbits of the hash value directly. For those applications which use the partial_name_hash(), move the multiply to end_name_hash. Signed-off-by: George Spelvin Signed-off-by: Linus Torvalds --- fs/dcache.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'fs/dcache.c') diff --git a/fs/dcache.c b/fs/dcache.c index 9522b8b63871..03f1a332f677 100644 --- a/fs/dcache.c +++ b/fs/dcache.c @@ -106,7 +106,7 @@ static struct hlist_bl_head *dentry_hashtable __read_mostly; static inline struct hlist_bl_head *d_hash(unsigned int hash) { - return dentry_hashtable + hash_32(hash, d_hash_shift); + return dentry_hashtable + (hash >> (32 - d_hash_shift)); } #define IN_LOOKUP_SHIFT 10 -- cgit