DCACHE hash using Jenkins

PATCH New David S. Miller 1 participant 1 message May 30, 2003

Subsystems (6)

VFS Char and misc drivers HFS filesystem Affs file system +2 more subsystems

lore

Share & tools

lore

David S. Miller

author

2003-05-30 10:34 UTC #0 lore raw

PATCH 1/1 DCACHE hash using Jenkins

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 renamed from drivers/char/mem.c.~1~ +0 -1

@@ -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 renamed from fs/adfs/dir.c.~1~ +4 -4

@@ -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 renamed from fs/affs/namei.c.~1~ +4 -4

@@ -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 renamed from fs/hfs/string.c.~1~ +4 -4

@@ -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 renamed from fs/hpfs/dentry.c.~1~ +4 -4

@@ -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 renamed from fs/isofs/inode.c.~1~ +4 -4

@@ -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 renamed from fs/minix/namei.c.~1~ +4 -4

@@ -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 renamed from fs/ncpfs/dir.c.~1~ +6 -5

@@ -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 renamed from fs/smbfs/dir.c.~1~ +4 -4

@@ -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 renamed from fs/sysv/namei.c.~1~ +4 -4

@@ -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 renamed from fs/vfat/namei.c.~1~ +4 -4

@@ -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 renamed from fs/dcache.c.~1~ +10 -0

@@ -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 renamed from fs/namei.c.~1~ +8 -8

@@ -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 renamed from include/linux/dcache.h.~1~ +54 ~~-19~~

106 lines not on this page · raw message

init/main.c renamed from init/main.c.~1~ +2 -0

@@ -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 renamed from kernel/ksyms.c.~1~ +1 -0

@@ -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);