dentry and inode cache hash algorithm performance changes.

err... Seems I've send this to the wrong list.
Sending to linux-kernel this time :)

-----------------------------------------------------------------------

Hi Andrew,

Could you consider this patch for inclusion into mainline kernel? It alleviates some issues seen with Linux when accessing millions of files on machines with large amounts of RAM (+32GB). Both algorithms are base on some studies that Dominique Heger was doing on hash table efficiencies in Linux. The dentry hash table has been tested in small systems with one internal IDE hard disk as well as in large SMP with many fiberchanel disks. Dominique claims that in all the testing done, they did not see one case were this has function provided worst performance and that in most test they were seeing better performance.

The inode hash function was done by me base on Dominique's original work and has only been stress tested with SpecSFS. It provided a 3% improvement over the default algorithm in the SpecSFS results and speed ups in the response time of almost all filesystem operations the benchmark stress. With the better distribution is as also possible to reduce the number of inode buckets for 32 million to 16 million and still get a slightly better results.

Anton was nice enough to provide some graphs that show the distribution before and after the patch at http://samba.org/~anton/linux/sfs/1/

Thanks

-JRS

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher. # This patch includes the following deltas:

#	           ChangeSet	1.1582  -> 1.1583 
#	         fs/dcache.c	1.70    -> 1.71   
#	          fs/inode.c	1.113   -> 1.114  

#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/04/30 [email protected] 1.1583
# Hash functions changes that show improvements on SpecSFS when a large amount of files is used (+20 Million). # --------------------------------------------
#

diff -Nru a/fs/dcache.c b/fs/dcache.c
@@ -28,6 +28,7 @@
 #include <asm/uaccess.h>
 #include <linux/security.h>
 #include <linux/seqlock.h>
+#include <linux/hash.h>
 
 #define DCACHE_PARANOIA 1
 /* #define DCACHE_DEBUG 1 */

@@ -799,8 +800,8 @@
 
 static inline struct hlist_head * d_hash(struct dentry * parent, unsigned long hash)
 {
-	hash += (unsigned long) parent / L1_CACHE_BYTES;
-	hash = hash ^ (hash >> D_HASHBITS);
+	hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
+	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
 	return dentry_hashtable + (hash & D_HASHMASK);
 }
 

diff -Nru a/fs/inode.c b/fs/inode.c
@@ -671,8 +671,9 @@
 
 static inline unsigned long hash(struct super_block *sb, unsigned long hashval)
 {
-	unsigned long tmp = hashval + ((unsigned long) sb / L1_CACHE_BYTES);
-	tmp = tmp + (tmp >> I_HASHBITS);
+	unsigned long tmp = (hashval + ((unsigned long) sb) ^ (GOLDEN_RATIO_PRIME + hashval)
+			/ L1_CACHE_BYTES);
+	tmp = tmp + ((tmp ^ GOLDEN_RATIO_PRIME) >> I_HASHBITS);
 	return tmp & I_HASHMASK;
 }
 

Judging from the graphs (!), I don't see a real difference for dcache. There's just one outlier (depth 11) for the old hash function, which seems to be translated to multiple depth 9 entries. The histograms seem to confirm, that there's at most a minimal difference, if they'd be equally scaled.

Maybe this is due to qstr hashes, which were used by both approaches as input?

The inode hash seems to be distributed more evenly with the new hash function. Although the inode histogram suggests, that most buckets are in the 0-2 depth range, with the old hash function leading slightly in the zero depth range.

Regards, Olaf.

SpecSFS is not really the best benchmark to show the efficiency of the dentry hash function. I need to come up with a better defense for the this hash functions. While I did not do the study for this hash function, mathematically speaking this hash algorithm should always create a equal or better hash. SFS just shows equal (well, slightly better), so Ill work on getting some more data to back up the "better" claim.

Thats a good thing. With the new hash function, we get 25% more bucket usage and most of the bucket are only 1 object deep. This buckets take
up memory so we better use them. The old hash functions was no very
efficient in spreading the hashes across all the buckets, with the new hash function we have 4.5 times more buckets with only 1 object deep so it scales better as we increase the number of buckets as well.

It also provides a 3% improvement on the overall SFS number with half the number of buckets use which I believe its a great improvement from just a hash algorithm change.

-JRS

Hi Jose,

Did u try the new hashing algorithm with dcache bench? dcachebench is focussed entirely on dcache performance. I had measured the performance of the dcachebench on 2.6.6 kernel with and without the new hashing algorithm and noticed significant decrease in performance with the new hash algorithm. Enclosed is the mail from LKML that dicusses this.

Also I wrote an instrumentation patch that measures the number of clock cycles spent by the hash and lookup. The hash time saw an increase(obviously) but I did see an increase in the time spent in the lookup function too. Attached is the patch I used for the instrumentation.

Thanks and Regards
Raghav

No, look again.

			old hash		new hash
	
	2.6.6:		10280			10496
	2.6.6-bk:	10685			10862

in both cases, the new hash makes each iteration about ~200us (or whatever the metric is) slower.

There's something _else_ going on too, since plain 2.6.6 is so clearly better than the others. I don't know why - the only thing -bk does is the hash change and some changes to GFP_NOFS behaviour (different return value from shrink_dentries or whatever). Which shouldn't even trigger, I'd have assumed this is all cached.

NOTE! Just "simple" things like variations in I$ layout of the kernel code can make a pretty big difference if you're unlucky. And the new dentry code doesn't align the things on a D$ cache line boundary, so there could easily be "consistent" differences from that - just from the order of dentries allocated etc.

But it's interesting to note that the hash does make a difference. The old hash was very much optimized for simplicity (those hash-calculation routines are some of the hottest in the kernel). But I don't see that a few extra instructions should make that big of a difference.

Linus

@@ -21,6 +21,7 @@
 #include <linux/slab.h>
 #include <linux/init.h>
 #include <linux/smp_lock.h>
+#include <linux/hash.h>
 #include <linux/cache.h>
 #include <linux/module.h>
 #include <linux/mount.h>

@@ -40,6 +41,19 @@ EXPORT_SYMBOL(dcache_lock);
 
 static kmem_cache_t *dentry_cache; 
 
+//#define OLD_HASH
+#define DB
+
+#ifdef DB
+#include <asm/processor.h>
+#include <asm/msr.h>
+#include <asm/e820.h>
+unsigned long  d_hash_count, d_lookup_count;
+unsigned long d_hash_misses, d_lookup_misses;
+unsigned long d_hash_overflow, d_lookup_overflow;
+unsigned long hash_array[250], lookup_array[500];
+#endif
+
 /*
  * This is the single most critical data structure when it comes
  * to the dcache: the hashtable for lookups. Somebody should try

@@ -643,24 +657,23 @@ void shrink_dcache_anon(struct hlist_hea
 }
 
 /*
- * This is called from kswapd when we think we need some more memory.
+ * Scan `nr' dentries and return the number which remain.
+ *
+ * We need to avoid reentering the filesystem if the caller is performing a
+ * GFP_NOFS allocation attempt.  One example deadlock is:
+ *
+ * ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
+ * prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->put_inode->
+ * ext2_discard_prealloc->ext2_free_blocks->lock_super->DEADLOCK.
+ *
+ * In this case we return -1 to tell the caller that we baled.
  */
 static int shrink_dcache_memory(int nr, unsigned int gfp_mask)
 {
 	if (nr) {
-		/*
-		 * Nasty deadlock avoidance.
-		 *
-	 	 * ext2_new_block->getblk->GFP->shrink_dcache_memory->
-		 * prune_dcache->prune_one_dentry->dput->dentry_iput->iput->
-		 * inode->i_sb->s_op->put_inode->ext2_discard_prealloc->
-		 * ext2_free_blocks->lock_super->DEADLOCK.
-	 	 *
-	 	 * We should make sure we don't hold the superblock lock over
-	 	 * block allocations, but for now:
-		 */
-		if (gfp_mask & __GFP_FS)
-			prune_dcache(nr);
+		if (!(gfp_mask & __GFP_FS))
+			return -1;
+		prune_dcache(nr);
 	}
 	return dentry_stat.nr_unused;
 }

@@ -795,11 +808,45 @@ struct dentry * d_alloc_root(struct inod
 	return res;
 }
 
-static inline struct hlist_head * d_hash(struct dentry * parent, unsigned long hash)
+static inline struct hlist_head *d_hash(struct dentry *parent,
+					unsigned long hash)
 {
+#ifdef DB
+        unsigned long long t1=0,t2=0;
+        preempt_disable();
+        rdtscll(t1);
+#endif
+
+#ifdef OLD_HASH
 	hash += (unsigned long) parent / L1_CACHE_BYTES;
 	hash = hash ^ (hash >> D_HASHBITS);
+#else
+	hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
+	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
+#endif
+
+#ifndef DB
 	return dentry_hashtable + (hash & D_HASHMASK);
+#else
+        rdtscll(t2);
+        preempt_enable();
+
+        if( d_hash_count < 0xffffffff )
+        {
+                if( (t2 > t1) && ( (t2 - t1) >= 0  ) && ((t2 - t1) < 5000))
+                {
+                        unsigned int c =  ((unsigned int)(t2 - t1)) /20;
+                        hash_array[c]++;
+                }
+                else
+                        d_hash_misses++;
+                d_hash_count++;
+        }
+        else d_hash_overflow++;
+
+        return dentry_hashtable + (hash & D_HASHMASK);
+#endif
+
 }
 
 /**

@@ -970,6 +1017,12 @@ struct dentry * __d_lookup(struct dentry
 	struct dentry *found = NULL;
 	struct hlist_node *node;
 
+#ifdef DB
+        unsigned long long t1=0,t2=0;
+        preempt_disable();
+        rdtscll(t1);
+#endif
+
 	rcu_read_lock();
 	
 	hlist_for_each (node, head) { 

@@ -1023,6 +1076,25 @@ struct dentry * __d_lookup(struct dentry
 		break;
  	}
  	rcu_read_unlock();
+#ifdef DB
+        rdtscll(t2);
+        preempt_enable();
+
+        if( d_lookup_count < 0xffffffff )
+        {
+                if( (t2 > t1) && ( (t2 - t1) >= 0  ) && ((t2 - t1) < 10000))
+                {
+                        unsigned int c =  ((unsigned int)(t2 - t1)) /20;
+                        lookup_array[c]++;
+                }
+                else
+                        d_lookup_misses++;
+                d_lookup_count++;
+        }
+        else d_lookup_overflow++;
+
+#endif
+
 
  	return found;
 }