VFS: use a proper hash function
authorBarret Rhoden <brho@cs.berkeley.edu>
Wed, 17 Sep 2014 22:58:39 +0000 (15:58 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Wed, 17 Sep 2014 22:58:39 +0000 (15:58 -0700)
Every dentry was getting 0xcafebabe for its hash value.  That put them all in
the same bucket in the dentry cache.  That made dcache lookups cost
O(nr_files_in_vfs), which was making opens (or any path lookup) take a long
time once we put the Go tree in KFS.  This even affected 9ns lookups, since
those check the VFS before trying 9ns.

kern/include/kfs.h
kern/include/vfs.h
kern/src/ext2fs.c
kern/src/kfs.c
kern/src/vfs.c

index 0e5c1db..84a9cad 100644 (file)
@@ -63,7 +63,6 @@ void kfs_truncate(struct inode *inode);
 int kfs_permission(struct inode *inode, int mode, struct nameidata *nd);
 /* dentry_operations */
 int kfs_d_revalidate(struct dentry *dir, struct nameidata *nd);
-int kfs_d_hash(struct dentry *dentry, struct qstr *name);
 int kfs_d_compare(struct dentry *dir, struct qstr *name1, struct qstr *name2);
 int kfs_d_delete(struct dentry *dentry);
 int kfs_d_release(struct dentry *dentry);
index fc33dba..32cd0c4 100644 (file)
@@ -444,6 +444,7 @@ struct dentry *dcache_get(struct super_block *sb, struct dentry *what_i_want);
 void dcache_put(struct super_block *sb, struct dentry *key_val);
 struct dentry *dcache_remove(struct super_block *sb, struct dentry *key);
 void dcache_prune(struct super_block *sb, bool negative_only);
+int generic_dentry_hash(struct dentry *dentry, struct qstr *qstr);
 
 /* Inode Functions */
 struct inode *get_inode(struct dentry *dentry);
index 9a88b42..ae7050b 100644 (file)
@@ -1270,12 +1270,6 @@ int ext2_d_revalidate(struct dentry *dir, struct nameidata *nd)
        return -1;
 }
 
-/* Produces the hash to lookup this dentry from the dcache */
-int ext2_d_hash(struct dentry *dentry, struct qstr *name)
-{
-       return -1;
-}
-
 /* Compares name1 and name2.  name1 should be a member of dir. */
 int ext2_d_compare(struct dentry *dir, struct qstr *name1, struct qstr *name2)
 { // default, string comp (case sensitive)
@@ -1481,7 +1475,7 @@ struct inode_operations ext2_i_op = {
 
 struct dentry_operations ext2_d_op = {
        ext2_d_revalidate,
-       ext2_d_hash,
+       generic_dentry_hash,
        ext2_d_compare,
        ext2_d_delete,
        ext2_d_release,
index 41d1019..3d9c457 100644 (file)
@@ -519,12 +519,6 @@ int kfs_d_revalidate(struct dentry *dir, struct nameidata *nd)
        return -1;
 }
 
-/* Produces the hash to lookup this dentry from the dcache */
-int kfs_d_hash(struct dentry *dentry, struct qstr *name)
-{
-       return -1;
-}
-
 /* Compares name1 and name2.  name1 should be a member of dir. */
 int kfs_d_compare(struct dentry *dir, struct qstr *name1, struct qstr *name2)
 { // default, string comp (case sensitive)
@@ -747,7 +741,7 @@ struct inode_operations kfs_i_op = {
 
 struct dentry_operations kfs_d_op = {
        kfs_d_revalidate,
-       kfs_d_hash,
+       generic_dentry_hash,
        kfs_d_compare,
        kfs_d_delete,
        kfs_d_release,
index 0cbceb0..f2d33db 100644 (file)
@@ -112,16 +112,26 @@ void vfs_init(void)
        printk("vfs_init() completed\n");
 }
 
+/* FS's can provide another, if they want */
+int generic_dentry_hash(struct dentry *dentry, struct qstr *qstr)
+{
+       unsigned long hash = 5381;
+
+       for (int i = 0; i < qstr->len; i++) {
+               /* hash * 33 + c, djb2's technique */
+               hash = ((hash << 5) + hash) + qstr->name[i];
+       }
+       return hash;
+}
+
 /* Builds / populates the qstr of a dentry based on its d_iname.  If there is an
  * l_name, (long), it will use that instead of the inline name.  This will
  * probably change a bit. */
 void qstr_builder(struct dentry *dentry, char *l_name)
 {
        dentry->d_name.name = l_name ? l_name : dentry->d_iname;
-       // TODO: pending what we actually do in d_hash
-       //dentry->d_name.hash = dentry->d_op->d_hash(dentry, &dentry->d_name); 
-       dentry->d_name.hash = 0xcafebabe;
        dentry->d_name.len = strnlen(dentry->d_name.name, MAX_FILENAME_SZ);
+       dentry->d_name.hash = dentry->d_op->d_hash(dentry, &dentry->d_name);
 }
 
 /* Useful little helper - return the string ptr for a given file */