[PATCH] DCACHE hash using Jenkins
From: David S. Miller (davem@redhat.com)
Date: Fri May 30 2003 - 05:50:50 EST
Scott and others, this implements the scheme I tried to describe in my
previous email. It is against current 2.5.x kernels, but little if
anything has changed in this area so the patch should be easy to
backport to 2.4.x versions too.
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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/