dcache scalability patch (2.4.17)

Here is the dcache scalability patch (cleaned up) as disscussed in the previous post to lkml by Dipankar. The patch uses RCU for doing fast dcache lookup. It also does lazy updates to lru list of dentries to avoid doing write operations while doing lookup.

Following changes were done in this version

o Removed the d_next_hash hack. Dentries are unhashed using list_del instead of list_del_init, and that too using d_drop interface
o Used d_drop_locked and d_unhashed instead of directly manipulating hash list using list macros
o Changed DCACHE_UNLINKED to DCACHE_UNHASHED

Regards,
Maneesh

diff -urN linux-2.4.17-base/fs/autofs4/root.c linux-2.4.17-dc8/fs/autofs4/root.c
@@ -403,7 +403,7 @@
 		spin_unlock(&dcache_lock);
 		return -ENOTEMPTY;
 	}
-	list_del_init(&dentry->d_hash);
+	d_drop_locked(dentry);
 	spin_unlock(&dcache_lock);
 
 	dput(ino->dentry);

diff -urN linux-2.4.17-base/fs/intermezzo/journal.c linux-2.4.17-dc8/fs/intermezzo/journal.c
@@ -186,7 +186,7 @@
 
         *--end = '\0';
         buflen--;
-        if (dentry->d_parent != dentry && list_empty(&dentry->d_hash)) {
+        if (dentry->d_parent != dentry && d_unhashed(dentry)) {
                 buflen -= 10;
                 end -= 10;
                 memcpy(end, " (deleted)", 10);

diff -urN linux-2.4.17-base/fs/nfsd/nfsfh.c linux-2.4.17-dc8/fs/nfsd/nfsfh.c
@@ -348,7 +348,7 @@
 	spin_lock(&dcache_lock);
 	list_for_each(lp, &child->d_inode->i_dentry) {
 		struct dentry *tmp = list_entry(lp,struct dentry, d_alias);
-		if (!list_empty(&tmp->d_hash) &&
+		if (!d_unhashed(tmp) &&
 		    tmp->d_parent == parent) {
 			child = dget_locked(tmp);
 			spin_unlock(&dcache_lock);

diff -urN linux-2.4.17-base/fs/readdir.c linux-2.4.17-dc8/fs/readdir.c
@@ -79,7 +79,7 @@
 			while(1) {
 				struct dentry *de = list_entry(list, struct dentry, d_child);
 
-				if (!list_empty(&de->d_hash) && de->d_inode) {
+  				if (!d_unhashed(de) && de->d_inode) {
 					spin_unlock(&dcache_lock);
 					if (filldir(dirent, de->d_name.name, de->d_name.len, filp->f_pos, de->d_inode->i_ino, DT_UNKNOWN) < 0)
 						break;

Maneesh Soni
IBM Linux Technology Center, 
IBM India Software Lab, Bangalore.
Phone: +91-80-5044999 email: [email protected]
http://lse.sourceforge.net/locking/rcupdate.html

Just to clarify from the project standpoint - we are *not* targeting 2.4.X. 2.4.X is what was used for ongoing performance measurement work and we had to hop on to that bandwagon. It was just a proof of concept.

We will publish the 2.5 stuff soon.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

Ok.. no problem.

I think this got left over becasue of some intermediate trials.. I have removed this now.

Sure..

I have note seen this but it should not be impossible.

Thanks for the review. I corrected the above two problems.. new patch is as below. As Dipankr said 2.4 version can be taken just as proof of concept and for disscussion.

Regards,
Maneesh

diff -urN linux-2.4.17-base/fs/autofs4/root.c linux-2.4.17-dc8/fs/autofs4/root.c
@@ -403,7 +403,7 @@
 		spin_unlock(&dcache_lock);
 		return -ENOTEMPTY;
 	}
-	list_del_init(&dentry->d_hash);
+	d_drop_locked(dentry);
 	spin_unlock(&dcache_lock);
 
 	dput(ino->dentry);

diff -urN linux-2.4.17-base/fs/intermezzo/journal.c linux-2.4.17-dc8/fs/intermezzo/journal.c
@@ -186,7 +186,7 @@
 
         *--end = '\0';
         buflen--;
-        if (dentry->d_parent != dentry && list_empty(&dentry->d_hash)) {
+        if (dentry->d_parent != dentry && d_unhashed(dentry)) {
                 buflen -= 10;
                 end -= 10;
                 memcpy(end, " (deleted)", 10);

diff -urN linux-2.4.17-base/fs/nfsd/nfsfh.c linux-2.4.17-dc8/fs/nfsd/nfsfh.c
@@ -348,7 +348,7 @@
 	spin_lock(&dcache_lock);
 	list_for_each(lp, &child->d_inode->i_dentry) {
 		struct dentry *tmp = list_entry(lp,struct dentry, d_alias);
-		if (!list_empty(&tmp->d_hash) &&
+		if (!d_unhashed(tmp) &&
 		    tmp->d_parent == parent) {
 			child = dget_locked(tmp);
 			spin_unlock(&dcache_lock);

diff -urN linux-2.4.17-base/fs/readdir.c linux-2.4.17-dc8/fs/readdir.c
@@ -79,7 +79,7 @@
 			while(1) {
 				struct dentry *de = list_entry(list, struct dentry, d_child);
 
-				if (!list_empty(&de->d_hash) && de->d_inode) {
+  				if (!d_unhashed(de) && de->d_inode) {
 					spin_unlock(&dcache_lock);
 					if (filldir(dirent, de->d_name.name, de->d_name.len, filp->f_pos, de->d_inode->i_ino, DT_UNKNOWN) < 0)
 						break;

Maneesh Soni
IBM Linux Technology Center, 
IBM India Software Lab, Bangalore.
Phone: +91-80-5044999 email: [email protected]
http://lse.sourceforge.net/locking/rcupdate.html

oops.. sorry.

This is the correct patch..

diff -urN linux-2.4.17-base/fs/autofs4/root.c linux-2.4.17-dc8/fs/autofs4/root.c
@@ -403,7 +403,7 @@
 		spin_unlock(&dcache_lock);
 		return -ENOTEMPTY;
 	}
-	list_del_init(&dentry->d_hash);
+	d_drop_locked(dentry);
 	spin_unlock(&dcache_lock);
 
 	dput(ino->dentry);

diff -urN linux-2.4.17-base/fs/intermezzo/journal.c linux-2.4.17-dc8/fs/intermezzo/journal.c
@@ -186,7 +186,7 @@
 
         *--end = '\0';
         buflen--;
-        if (dentry->d_parent != dentry && list_empty(&dentry->d_hash)) {
+        if (dentry->d_parent != dentry && d_unhashed(dentry)) {
                 buflen -= 10;
                 end -= 10;
                 memcpy(end, " (deleted)", 10);

diff -urN linux-2.4.17-base/fs/nfsd/nfsfh.c linux-2.4.17-dc8/fs/nfsd/nfsfh.c
@@ -348,7 +348,7 @@
 	spin_lock(&dcache_lock);
 	list_for_each(lp, &child->d_inode->i_dentry) {
 		struct dentry *tmp = list_entry(lp,struct dentry, d_alias);
-		if (!list_empty(&tmp->d_hash) &&
+		if (!d_unhashed(tmp) &&
 		    tmp->d_parent == parent) {
 			child = dget_locked(tmp);
 			spin_unlock(&dcache_lock);

diff -urN linux-2.4.17-base/fs/readdir.c linux-2.4.17-dc8/fs/readdir.c
@@ -79,7 +79,7 @@
 			while(1) {
 				struct dentry *de = list_entry(list, struct dentry, d_child);
 
-				if (!list_empty(&de->d_hash) && de->d_inode) {
+  				if (!d_unhashed(de) && de->d_inode) {
 					spin_unlock(&dcache_lock);
 					if (filldir(dirent, de->d_name.name, de->d_name.len, filp->f_pos, de->d_inode->i_ino, DT_UNKNOWN) < 0)
 						break;

Maneesh Soni
IBM Linux Technology Center, 
IBM India Software Lab, Bangalore.
Phone: +91-80-5044999 email: [email protected]
http://lse.sourceforge.net/locking/rcupdate.html

Where is
* version for 2.5.<current>
* analysis of benefits in real-world situations for 2.5 version?

Patch adds complexity and unless you can show that it gives significant benefits outside of pathological situations, it's not going in.

Note: measurements on 2.4 do not make sense; reduction of cacheline bouncing between 2.4 and 2.5 will change the results anyway and if any of these patches are going to be applied to 2.4, reduction of cacheline bouncing on ->d_count is going to go in before that one.

I know that 2.5 patches are available, but Maneesh will probably respond to this on Monday.

I am working on getting 2.5 measurements done. BTW, would you consider specweb99 reasonably real-world ? If not, do you have any suggestions for benchmarks ? I suspect that dbench wouldn't cut it ;-).

Fair enough.

Quite possible. Our performance measurements have been far behind and we are catching up now. You may expect 2.5 numbers soon.

That is an issue we need to work on. We can do some cache event profiling to understand the extent of the d_count cacheline bouncing. At the same time, it seems that the dcache_lock cacheline is also bouncing around and it is probably more shared than the dentries for / or /usr. One thing for sure - RCU based lookup of dcache makes it difficult to optimize on dget()s. We will have to figure out a way to do this.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

Hi Al,

Mark Hahn made a good point over private email that real-worldness also includes hardware. I will dig around and see if we can work out a setup with different dual/4CPU hardware to do webserver benchmarks and analyze results for 2.5 patches.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

Dipankar,

I just loaded a 2-way PII 400Mhz with 256Meg of ram which
is a lot more real world than most the other systems we test. It is on the net (behind the ibm firewall of course) so you can use it if you want.

Hanna

I think there are some other possibilities for cache-bounce removal in struct dentry. The most obvious one is d_vfs_flags - not only does it get written to on every d_lookup (to set DCACHE_REFERENCED) but it also shares a cache line (on Pentium IV) with d_op, d_iname and part of d_name (along with d_sb and d_fsdata, but these don't seem to be so crucial).

Some quick stats gathering suggested that DCACHE_REFERENCED is already set 95%-98% of the time, so this cache bounce is not even doing anything useful. I submitted this patch a while ago making the DCACHE_REFERENCED bit setting be conditional on it not being already set, which didn't generate any interest. One problem with this patch would be the additional branch prediction misses (on some architectures?) that would work against the benefits of not dirtying a cache line.

Maybe we should have a function definition something like the following:

static __inline__ void __ensure_bit_set(int nr, volatile unsigned long * addr) {

#if defined (CONFIG_BIG_SMP) || defined(ARCH_HAVE_PREDICATED_WRITE)
	if(!test_bit(nr, addr))
#endif
		set_bit(nr, addr);
}	

so that architectures that support conditional writes (arm and ia64?) and for SMP systems with enough processors that cache-bouncing is an issue, the test can be performed, and for others where the branch prediction miss would hurt us more than the cache dirtying it would just do it unconditionally.

@@ -883,7 +883,8 @@
 			if (memcmp(dentry->d_name.name, str, len))
 				continue;
 		}
-		dentry->d_vfs_flags |= DCACHE_REFERENCED;
+		if(!(dentry->d_vfs_flags & DCACHE_REFERENCED))
+			dentry->d_vfs_flags |= DCACHE_REFERENCED;
 		return dentry;
 	}
 	return NULL;

Perhaps another solution is to rearrange struct dentry - put the volatile stuff in one cache line (or set of lines), and the constant stuff in another. So probably d_count, d_lru and d_vfs_flags would be in the volatile line, and most other stuff in the the other.

It would probably make sense to ensure that d_name and d_iname share a cache line if possible, even on smaller cache-line architectures, and maybe also d_hash and d_parent on that same line.

Paul

Frankly, I'd rather moved setting DCACHE_REFERENCED to dput(). We don't care for that bit for dentries with positive ->d_count.

So I'd just do

vi fs/dcache.c -c '/|= DCACHE_R/d|/nr_un/pu|<|x'

and be done with that. Linus?

Some possibly minor issues with that:

- accessing foo/../bar, won't mark foo as referenced, even though it might be being referenced frequently. Probably not a common case for foo to be accessed exclusively in this way, but it could be fixed by marking a dentry referenced when following ".."

- currently, negative dentries start off unreferenced and get marked referenced the second and subsequent time that they're used. This would change to starting off referenced (by the ref count set in lock_nd() after the ->lookup()) but then not being marked referenced ever again, as they're always looked at under dcache_lock, and no count is taken on them. So used-once negative dentries would hang around longer, and frequently-used negative dentries would be cleaned up sooner.

- referenced bit will be set possibly long after the reference is actually taken/used, which might make dentry pruning a little less accurate.

I was considering suggesting moving the reference bit setting to unlock_nd(), since that's another place where we're already changing d_count, but that still has the first two problems that I mentioned. Either way, moving d_vfsflags to the same cacheline as d_count would probably be a good idea.

Paul

It certainly will. Look - until ->d_count hits zero referenced bit is not touched or looked at. At all.

Look at the code. There is _no_ aging for dentries with positive ->d_count. They start aging only when after they enter unused_list...

Yes, but with the fastwalk lookup, accessing foo/../bar won't do a dget() for foo (assuming it was cached), and hence will never do a dput() on it either. So if the only references to foo are as foo/../bar then its d_count will stay zero and it will never be marked referenced. (Or am I missing something?)

Paul

On the second thought, I should apply that advice myself. It's true
that they start aging only after they hit the unused list, but they are born old. Hrm...

OK, it kills that variant and it really looks like there's no way
around dirtying dentry first time we find it on d_lookup(). Which means that we probably want to put that |= under if - without any ifdefs...

Done.

For future reference - don't anybody else try to send patches as vi scripts, please. Yes, it's manly, but let's face it, so is bungee-jumping with the cord tied to your testicles.

Linus

Here are the slides where I presented, among other things, some performance results of fastwalk compared to using rcu with lazy updating of the d_lru list. The results are similar to what Dipankar just published but there are a few more data points.

http://lse.sf.net/locking

Thanks.

Hanna

Hi Viro,

The 2.4 tests we did, also has fastwalk patch ported from 2.5. Though fastwalk has performed better (throughput improved by 1%) than base 2.4 but I think because of increased hold and wait times on dcache_lock, results are not as good as using only dcache_rcu.

	http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2

For 2.5 I tried to merge fastwalk and dcache_rcu but both doesnot seem to compliment each other. fastwalk takes dcache_lock much earlier than d_lookup.

On 2.5 we get better results from dcache_rcu when we reomve fastwalk and put the dcache code back to 2.5.10ish level of code. Probably this is not the correct way as it involves lots of code changes and we need to workout some other way.

There are some numbers from 2.5.20-base vs dcache_rcu(no fastwalk) done by Anton Blanchard with dbench.

	http://samba.org/~anton/linux/2.5.20/

Regards,
Maneesh

Maneesh Soni
IBM Linux Technology Center, 
IBM India Software Lab, Bangalore.
Phone: +91-80-5044999 email: [email protected]
http://lse.sourceforge.net/locking/rcupdate.html