The hash state accumulates name string bytes into a 3-word state
area. Once the state area is full _OR_ we are finishing the hash
we run a __jhash_mix() pass.
The rest are just mindless edits to fix all the interface users.
This is just a hack, one obvious improvement is to uninlinine these
foo_name_hash things now that they expand to a non-trivial amount of
code.
--- ./drivers/char/mem.c.~1~ Fri May 30 02:36:32 2003
+++ ./drivers/char/mem.c Fri May 30 02:36:40 2003
@@ -695,7 +695,6 @@ static int __init chr_dev_init(void)
S_IFCHR | devlist[i].mode, devlist[i].name);
}
- rand_initialize();
#if defined (CONFIG_FB)
fbmem_init();
#endif
--- ./fs/adfs/dir.c.~1~ Fri May 30 00:59:14 2003
+++ ./fs/adfs/dir.c Fri May 30 00:59:47 2003
@@ -208,7 +208,7 @@ adfs_hash(struct dentry *parent, struct
{
const unsigned int name_len = ADFS_SB(parent->d_sb)->s_namelen;
const unsigned char *name;
- unsigned long hash;
+ struct name_hash_state hash;
int i;
if (qstr->len < name_len)
@@ -220,7 +220,7 @@ adfs_hash(struct dentry *parent, struct
*/
qstr->len = i = name_len;
name = qstr->name;
- hash = init_name_hash();
+ init_name_hash(&hash);
while (i--) {
char c;
@@ -228,9 +228,9 @@ adfs_hash(struct dentry *parent, struct
if (c >= 'A' && c <= 'Z')
c += 'a' - 'A';
- hash = partial_name_hash(c, hash);
+ partial_name_hash(c, &hash);
}
- qstr->hash = end_name_hash(hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/affs/namei.c.~1~ Fri May 30 00:59:59 2003
+++ ./fs/affs/namei.c Fri May 30 01:00:21 2003
@@ -74,18 +74,18 @@ static inline int
__affs_hash_dentry(struct dentry *dentry, struct qstr *qstr, toupper_t toupper)
{
const u8 *name = qstr->name;
- unsigned long hash;
+ struct name_hash_state hash;
int i;
i = affs_check_name(qstr->name,qstr->len);
if (i)
return i;
- hash = init_name_hash();
+ init_name_hash(&hash);
i = min(qstr->len, 30u);
for (; i > 0; name++, i--)
- hash = partial_name_hash(toupper(*name), hash);
- qstr->hash = end_name_hash(hash);
+ partial_name_hash(toupper(*name), &hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/hfs/string.c.~1~ Fri May 30 01:00:48 2003
+++ ./fs/hfs/string.c Fri May 30 01:01:14 2003
@@ -83,12 +83,12 @@ static unsigned char casefold[256] = {
*/
unsigned int hfs_strhash(const unsigned char *name, unsigned int len)
{
- unsigned long hash = init_name_hash();
+ struct name_hash_state hash;
+ init_name_hash(&hash);
while (len--)
- hash = partial_name_hash(caseorder[*name++],
- hash);
- return end_name_hash(hash);
+ partial_name_hash(caseorder[*name++], &hash);
+ return end_name_hash(&hash);
}
/*
--- ./fs/hpfs/dentry.c.~1~ Fri May 30 01:01:34 2003
+++ ./fs/hpfs/dentry.c Fri May 30 01:02:06 2003
@@ -14,7 +14,7 @@
int hpfs_hash_dentry(struct dentry *dentry, struct qstr *qstr)
{
- unsigned long hash;
+ struct name_hash_state hash;
int i;
unsigned l = qstr->len;
@@ -26,10 +26,10 @@ int hpfs_hash_dentry(struct dentry *dent
/*return -ENOENT;*/
x:
- hash = init_name_hash();
+ init_name_hash(&hash);
for (i = 0; i < l; i++)
- hash = partial_name_hash(hpfs_upcase(hpfs_sb(dentry->d_sb)->sb_cp_table,qstr->name[i]), hash);
- qstr->hash = end_name_hash(hash);
+ partial_name_hash(hpfs_upcase(hpfs_sb(dentry->d_sb)->sb_cp_table,qstr->name[i]), &hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/isofs/inode.c.~1~ Fri May 30 01:02:14 2003
+++ ./fs/isofs/inode.c Fri May 30 01:02:32 2003
@@ -211,7 +211,7 @@ isofs_hashi_common(struct dentry *dentry
const char *name;
int len;
char c;
- unsigned long hash;
+ struct name_hash_state hash;
len = qstr->len;
name = qstr->name;
@@ -220,12 +220,12 @@ isofs_hashi_common(struct dentry *dentry
len--;
}
- hash = init_name_hash();
+ init_name_hash(&hash);
while (len--) {
c = tolower(*name++);
- hash = partial_name_hash(tolower(c), hash);
+ partial_name_hash(tolower(c), &hash);
}
- qstr->hash = end_name_hash(hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/minix/namei.c.~1~ Fri May 30 01:02:46 2003
+++ ./fs/minix/namei.c Fri May 30 01:03:06 2003
@@ -32,7 +32,7 @@ static int add_nondir(struct dentry *den
static int minix_hash(struct dentry *dentry, struct qstr *qstr)
{
- unsigned long hash;
+ struct name_hash_state hash;
int i;
const unsigned char *name;
@@ -43,10 +43,10 @@ static int minix_hash(struct dentry *den
function. */
qstr->len = i;
name = qstr->name;
- hash = init_name_hash();
+ init_name_hash(&hash);
while (i--)
- hash = partial_name_hash(*name++, hash);
- qstr->hash = end_name_hash(hash);
+ partial_name_hash(*name++, &hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/ncpfs/dir.c.~1~ Fri May 30 01:03:20 2003
+++ ./fs/ncpfs/dir.c Fri May 30 01:03:50 2003
@@ -101,17 +101,18 @@ static int
ncp_hash_dentry(struct dentry *dentry, struct qstr *this)
{
struct nls_table *t;
- unsigned long hash;
int i;
t = NCP_IO_TABLE(dentry);
if (!ncp_case_sensitive(dentry->d_inode)) {
- hash = init_name_hash();
+ struct name_hash_state hash;
+
+ init_name_hash(&hash);
for (i=0; i<this->len ; i++)
- hash = partial_name_hash(ncp_tolower(t, this->name[i]),
- hash);
- this->hash = end_name_hash(hash);
+ partial_name_hash(ncp_tolower(t, this->name[i]),
+ &hash);
+ this->hash = end_name_hash(&hash);
}
return 0;
}
--- ./fs/smbfs/dir.c.~1~ Fri May 30 01:04:05 2003
+++ ./fs/smbfs/dir.c Fri May 30 01:04:22 2003
@@ -330,13 +330,13 @@ smb_lookup_validate(struct dentry * dent
static int
smb_hash_dentry(struct dentry *dir, struct qstr *this)
{
- unsigned long hash;
+ struct name_hash_state hash;
int i;
- hash = init_name_hash();
+ init_name_hash(&hash);
for (i=0; i < this->len ; i++)
- hash = partial_name_hash(tolower(this->name[i]), hash);
- this->hash = end_name_hash(hash);
+ partial_name_hash(tolower(this->name[i]), &hash);
+ this->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/sysv/namei.c.~1~ Fri May 30 01:04:34 2003
+++ ./fs/sysv/namei.c Fri May 30 01:04:51 2003
@@ -42,7 +42,7 @@ static int add_nondir(struct dentry *den
static int sysv_hash(struct dentry *dentry, struct qstr *qstr)
{
- unsigned long hash;
+ struct name_hash_state hash;
int i;
const unsigned char *name;
@@ -53,10 +53,10 @@ static int sysv_hash(struct dentry *dent
function. */
qstr->len = i;
name = qstr->name;
- hash = init_name_hash();
+ init_name_hash(&hash);
while (i--)
- hash = partial_name_hash(*name++, hash);
- qstr->hash = end_name_hash(hash);
+ partial_name_hash(*name++, &hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/vfat/namei.c.~1~ Fri May 30 01:05:02 2003
+++ ./fs/vfat/namei.c Fri May 30 01:05:25 2003
@@ -139,17 +139,17 @@ static int vfat_hashi(struct dentry *den
struct nls_table *t = MSDOS_SB(dentry->d_inode->i_sb)->nls_io;
const char *name;
int len;
- unsigned long hash;
+ struct name_hash_state hash;
len = qstr->len;
name = qstr->name;
while (len && name[len-1] == '.')
len--;
- hash = init_name_hash();
+ init_name_hash(&hash);
while (len--)
- hash = partial_name_hash(vfat_tolower(t, *name++), hash);
- qstr->hash = end_name_hash(hash);
+ partial_name_hash(vfat_tolower(t, *name++), &hash);
+ qstr->hash = end_name_hash(&hash);
return 0;
}
--- ./fs/dcache.c.~1~ Fri May 30 01:09:34 2003
+++ ./fs/dcache.c Fri May 30 03:32:07 2003
@@ -28,6 +28,8 @@
#include <asm/uaccess.h>
#include <linux/security.h>
#include <linux/seqlock.h>
+#include <linux/random.h>
+#include <linux/init.h>
#define DCACHE_PARANOIA 1
/* #define DCACHE_DEBUG 1 */
@@ -53,6 +55,8 @@ static unsigned int d_hash_shift;
static struct hlist_head *dentry_hashtable;
static LIST_HEAD(dentry_unused);
+u32 dcache_hash_rnd;
+
/* Statistics gathering. */
struct dentry_stat_t dentry_stat = {
.age_limit = 45,
@@ -1596,6 +1600,12 @@ static void __init dcache_init(unsigned
d++;
i--;
} while (i);
+
+ /* The name hash routines start by BUG checking that
+ * dcache_hash_rnd is non-zero.
+ */
+ while (!dcache_hash_rnd)
+ get_random_bytes(&dcache_hash_rnd, sizeof(dcache_hash_rnd));
}
/* SLAB cache for __getname() consumers */
--- ./fs/namei.c.~1~ Fri May 30 01:05:41 2003
+++ ./fs/namei.c Fri May 30 01:06:27 2003
@@ -582,7 +582,7 @@ int link_path_walk(const char * name, st
/* At this point we know we have a real path component. */
for(;;) {
- unsigned long hash;
+ struct name_hash_state hash;
struct qstr this;
unsigned int c;
@@ -596,14 +596,14 @@ int link_path_walk(const char * name, st
this.name = name;
c = *(const unsigned char *)name;
- hash = init_name_hash();
+ init_name_hash(&hash);
do {
name++;
- hash = partial_name_hash(c, hash);
+ partial_name_hash(c, &hash);
c = *(const unsigned char *)name;
} while (c && (c != '/'));
this.len = name - (const char *) this.name;
- this.hash = end_name_hash(hash);
+ this.hash = end_name_hash(&hash);
/* remove trailing slashes? */
if (!c)
@@ -908,7 +908,7 @@ out:
/* SMP-safe */
struct dentry * lookup_one_len(const char * name, struct dentry * base, int len)
{
- unsigned long hash;
+ struct name_hash_state hash;
struct qstr this;
unsigned int c;
@@ -917,14 +917,14 @@ struct dentry * lookup_one_len(const cha
if (!len)
goto access;
- hash = init_name_hash();
+ init_name_hash(&hash);
while (len--) {
c = *(const unsigned char *)name++;
if (c == '/' || c == '\0')
goto access;
- hash = partial_name_hash(c, hash);
+ partial_name_hash(c, &hash);
}
- this.hash = end_name_hash(hash);
+ this.hash = end_name_hash(&hash);
return lookup_hash(&this, base);
access:
--- ./include/linux/dcache.h.~1~ Fri May 30 00:06:47 2003
+++ ./include/linux/dcache.h Fri May 30 02:18:37 2003
@@ -3,11 +3,13 @@
#ifdef __KERNEL__
+#include <linux/types.h>
#include <asm/atomic.h>
#include <linux/list.h>
#include <linux/spinlock.h>
#include <linux/cache.h>
#include <linux/rcupdate.h>
+#include <linux/jhash.h>
#include <asm/bug.h>
struct vfsmount;
@@ -30,7 +32,7 @@ struct vfsmount;
struct qstr {
const unsigned char * name;
unsigned int len;
- unsigned int hash;
+ u32 hash;
char name_str[0];
};
@@ -43,34 +45,67 @@ struct dentry_stat_t {
};
extern struct dentry_stat_t dentry_stat;
-/* Name hashing routines. Initial hash value */
-/* Hash courtesy of the R5 hash in reiserfs modulo sign bits */
-#define init_name_hash() 0
-
-/* partial hash update function. Assume roughly 4 bits per character */
-static inline unsigned long
-partial_name_hash(unsigned long c, unsigned long prevhash)
+extern u32 dcache_hash_rnd;
+
+struct name_hash_state {
+ u32 words[3];
+ u32 cur_byte;
+};
+
+/* Name hashing routines. */
+static inline void
+init_name_hash(struct name_hash_state *hash)
{
- return (prevhash + (c << 4) + (c >> 4)) * 11;
+ if (!dcache_hash_rnd)
+ BUG();
+ hash->words[0] = hash->words[1] = JHASH_GOLDEN_RATIO;
+ hash->words[2] = dcache_hash_rnd;
+ hash->cur_byte = 0;
}
-/*
- * Finally: cut down the number of bits to a int value (and try to avoid
- * losing bits)
- */
-static inline unsigned long end_name_hash(unsigned long hash)
+static inline void
+partial_name_hash(const unsigned char c, struct name_hash_state *hash)
{
- return (unsigned int) hash;
+ u32 entry = hash->cur_byte;
+ u32 val = (u32) c << ((entry % sizeof(u32)) * 8);
+
+ hash->words[entry / sizeof(u32)] += val;
+ if (++hash->cur_byte == 12) {
+ u32 a = hash->words[0], b = hash->words[1], c = hash->words[2];
+
+ __jhash_mix(a, b, c);
+
+ hash->words[0] = a;
+ hash->words[1] = b;
+ hash->words[2] = c;
+
+ hash->cur_byte = 0;
+ }
+}
+
+static inline u32 end_name_hash(struct name_hash_state *hash)
+{
+ u32 c = hash->words[2];
+
+ if (hash->cur_byte) {
+ u32 a = hash->words[0], b = hash->words[1];
+
+ c = hash->words[2];
+ __jhash_mix(a, b, c);
+ }
+ return c;
}
/* Compute the hash for a name string. */
-static inline unsigned int
+static inline u32
full_name_hash(const unsigned char *name, unsigned int len)
{
- unsigned long hash = init_name_hash();
+ struct name_hash_state hash;
+
+ init_name_hash(&hash);
while (len--)
- hash = partial_name_hash(*name++, hash);
- return end_name_hash(hash);
+ partial_name_hash(*name++, &hash);
+ return end_name_hash(&hash);
}
#define DNAME_INLINE_LEN_MIN 16
--- ./init/main.c.~1~ Fri May 30 03:30:09 2003
+++ ./init/main.c Fri May 30 03:33:06 2003
@@ -37,6 +37,7 @@
#include <linux/rcupdate.h>
#include <linux/moduleparam.h>
#include <linux/writeback.h>
+#include <linux/random.h>
#include <asm/io.h>
#include <asm/bugs.h>
@@ -437,6 +438,7 @@ asmlinkage void __init start_kernel(void
proc_caches_init();
security_scaffolding_startup();
buffer_init();
+ rand_initialize();
vfs_caches_init(num_physpages);
radix_tree_init();
signals_init();
--- ./kernel/ksyms.c.~1~ Fri May 30 01:09:48 2003
+++ ./kernel/ksyms.c Fri May 30 01:10:14 2003
@@ -160,6 +160,7 @@ EXPORT_SYMBOL(lookup_one_len);
EXPORT_SYMBOL(lookup_hash);
EXPORT_SYMBOL(sys_close);
EXPORT_SYMBOL(dcache_lock);
+EXPORT_SYMBOL(dcache_hash_rnd);
EXPORT_SYMBOL(d_alloc_root);
EXPORT_SYMBOL(d_delete);
EXPORT_SYMBOL(dget_locked);
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/