Skip to contentSkip to conversation

Peeling off dcache_lock

RFC New Maneesh Soni 3 participants 5 messages Jan 21, 2002 – Feb 12, 2002

Subsystems (6)
VFS NFS client NFS server File locking (flock() and fcntl()/lockf()) +2 more subsystems
lore
Share & tools
lore

Maneesh Soni

author
#0 lore raw

Hi All,

We have been doing experiments with dcache_lock to provide some relief from it. Though dcache_lock is not a very hot lock in comparision to BKL but on higher end machines it becomes quite contentious. We would like to have feedbacks, comments about the approach taken and guidance on how to improve this further.

As dcache_lock is acquired maximum number of times while doing lookup, the main idea was to remove dcache_lock from d_lookup. With the help of Read Copy Update it is possible to lookup the hash list of dentries without taking dcache_lock but as d_lookup also updates the lru list, removing dcache_lock from d_lookup was not straight forward. Various approaches were tried for that and the most successful is doing lazy updation of lru list.

Using this the dcache_lock contention was down from 16.5% to 0.95% on an 8-way SMP box and lock utilization was down from 5.3% to 0.89%

The patch for lazy lru updation using RCU can be found here:

http://lse.sourceforge.net/locking/dcache/patches/2.4.17/dcache_rcu-lazy_lru-2.4.17-06.patch

The basic conecpt for this approach is to not update the lru list in d_lookup facilitating lockless d_lookup. The lru list can now have dentries with non zero reference count also. The lru list is updated while pruning dentry cache. The dcache_lock is kept around so that there are no changes in the update side locking.

The implementation details for lazy lru list updation and other approaches can be found here:

http://lse.sourceforge.net/locking/dcache/dcache_lock.html

The above patch works fine with various file systems like ext2, JFS, ext3, /procand has been tested ok with ltp-20020108, dbench, httperf. And doesnot not have any adverse effects on uni processor performance.

Regards,
Maneesh

Signature · 5 lines
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
#1 lore raw
Quoted 6 lines · On Mon, 21 Jan 2002 17:40:39 +0530 Maneesh Soni <[email protected]> wrote:

Hi All,

We have been doing experiments with dcache_lock to provide some relief from it. Though dcache_lock is not a very hot lock in comparision to BKL but on higher end machines it becomes quite contentious. We would like to have feedbacks, comments about the approach taken and guidance on how to improve this further.

Hi Maneesh!

Fantastic work! A couple of questions, and a trivial patch:

o Would DCACHE_DEFERRED_FREE be better called DCACHE_UNLINKED? If I understand correctly, it's only and always set when someone has deleted (unhashed) the dentry.

o Am I correct in asserting that you could change all the "list_empty(dentry->dhash)" tests to
"dentry->d_vfs_flags & DCACHE_DEFERRED_FREE" tests, and hence change the list_del_init() to list_del() in unhash, and thus remove the d_nexthash field altogether?

o d_lookup looks like it can return an DCACHE_DEFERRED_FREE dentry: this seems wrong: shouldn't it loop here?

o Were you planning on changing d_count to a non-atomic? It seems overkill to have it protected by the lock, but ALSO atomic for other places. Could be a performance loss as well.

o Minor nitpick: unhash() in dcache.h is plainer implemented in terms of __unhash().

Any chance of you making it to http://linux.conf.au next month BTW?

Thanks for the cool patch!
Rusty.

Signature · 1 line
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
#2 lore raw
In reply to Maneesh Soni

Since there has been speculation about the throughput #s for lower end, I have put up the comparison graph in the same page
(http://lse.sf.net/locking/dcache/dcache_lock.html).

As http://lse.sourceforge.net/locking/dcache/results/dbench/base+dc-tpt.png
would show, there is *no* performance degradation at the lower end or UP. The absolute numbers are in
http://lse.sourceforge.net/locking/dcache/results/dbench/.

Thanks
Dipankar

Signature · 2 lines
Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.
Quoted 46 lines · Maneesh Soni

Hi All,

We have been doing experiments with dcache_lock to provide some relief from it. Though dcache_lock is not a very hot lock in comparision to BKL but on higher end machines it becomes quite contentious. We would like to have feedbacks, comments about the approach taken and guidance on how to improve this further.

As dcache_lock is acquired maximum number of times while doing lookup, the main idea was to remove dcache_lock from d_lookup. With the help of Read Copy Update it is possible to lookup the hash list of dentries without taking dcache_lock but as d_lookup also updates the lru list, removing dcache_lock from d_lookup was not straight forward. Various approaches were tried for that and the most successful is doing lazy updation of lru list.

Using this the dcache_lock contention was down from 16.5% to 0.95% on an 8-way SMP box and lock utilization was down from 5.3% to 0.89%

The patch for lazy lru updation using RCU can be found here:

http://lse.sourceforge.net/locking/dcache/patches/2.4.17/dcache_rcu-lazy_lru-2.4.17-06.patch

The basic conecpt for this approach is to not update the lru list in d_lookup facilitating lockless d_lookup. The lru list can now have dentries with non zero reference count also. The lru list is updated while pruning dentry cache. The dcache_lock is kept around so that there are no changes in the update side locking.

The implementation details for lazy lru list updation and other approaches can be found here:

http://lse.sourceforge.net/locking/dcache/dcache_lock.html

The above patch works fine with various file systems like ext2, JFS, ext3, /procand has been tested ok with ltp-20020108, dbench, httperf. And doesnot not have any adverse effects on uni processor performance.

Regards,
Maneesh

Signature · 5 lines
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
#3 lore raw
Quoted 3 lines · On Fri, 25 Jan 2002 15:00:00 +0530 Dipankar Sarma <[email protected]> wrote:

Since there has been speculation about the throughput #s for lower end, I have put up the comparison graph in the same page
(http://lse.sf.net/locking/dcache/dcache_lock.html).

Have you thought about getting rid of the lru list altogether, and traverse one chain at a time in prune_dcache, using the referenced bit as a straight clock algorithm:

	spin_lock(&dentry->d_lock);
	if (atomic_read(dentry->dcount) == 0) {
		if (dentry->d_vfs_flags & DCACHE_REFERENCED)
			dentry->d_vfs_flags &= ~DCACHE_REFERENCED;
		else
			prune_one_dentry(dentry);
	}
	spin_unlock(&dentry->d_lock);

This can be optimized by doing a dcount check outside the loop, and the global dcache lock can be dropped between each hash chain, and we can store the last traversed hash chain in a static var, protected by the global lock.

I'm just not sure how much the "semi" LRU wins us... Rusty.

Signature · 1 line
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
author
#4 lore raw

RFC PATCH 1/1 Peeling off dcache_lock - Ver 2

In reply to Maneesh Soni

This is the cleaned up dcache patch using Read-Copy update and lazy lru list updation logic from
http://lse.sourceforge.net/locking/dcache/dcache_lock.html

The cleanups were suggested by Rusty Russell.

Change log:

o  New patch name.
o  Better name for DCACHE_DEFERRED_FREE, now it is DCACHE_UNLINKED
o  Removed d_nexthash from struct dentry and replaced all

list_empty(dentry->d_hash) with d_unhashed(dentry).
o Changed d_count to non-atomic as all updates to d_count are done under per dentry lock.
o Changed unhash() & __unhash() to dentry_unhash() and __dentry_unhash(). dentry_unhash() just calls __dentry_unhash() with per dentry lock held.

dcache_rcu-2.4.17-2.patch:

fs/autofs4/expire.c +11 -5
diff -urN linux-2.4.17/fs/autofs4/expire.c linux-2.4.17-dcache_rcu-2/fs/autofs4/expire.c
@@ -84,7 +84,8 @@
 	struct list_head *next;
 	int count;
 
-	count = atomic_read(&top->d_count);
+	spin_lock(&top->d_lock);
+	count = top->d_count;
 	
 	DPRINTK(("is_tree_busy: top=%p initial count=%d\n", 
 		 top, count));

@@ -107,7 +108,8 @@
 						   d_child);
 		next = next->next;
 
-		count += atomic_read(&dentry->d_count) - 1;
+		spin_lock(&dentry->d_lock);
+		count += dentry->d_count - 1;
 
 		if (d_mountpoint(dentry))
 			adj += check_vfsmnt(topmnt, dentry);

@@ -121,15 +123,18 @@
 		count -= adj;
 
 		if (!list_empty(&dentry->d_subdirs)) {
+			spin_unlock(&dentry->d_lock);
 			this_parent = dentry;
 			goto repeat;
 		}
 
-		if (atomic_read(&dentry->d_count) != adj) {
+		if (dentry->d_count != adj) {
 			DPRINTK(("is_tree_busy: busy leaf (d_count=%d adj=%d)\n",
-				 atomic_read(&dentry->d_count), adj));
+				 dentry->d_count, adj));
+			spin_unlock(&dentry->d_lock);
 			return 1;
 		}
+		spin_unlock(&dentry->d_lock);
 	}
 
 	/* All done at this level ... ascend and resume the search. */

@@ -137,7 +142,8 @@
 		next = this_parent->d_child.next; 
 		this_parent = this_parent->d_parent;
 		goto resume;
-	}
+	}	
+	spin_unlock(&top->d_lock);
 
 	DPRINTK(("is_tree_busy: count=%d\n", count));
 	return count != 0; /* remaining users? */
fs/autofs4/root.c +1 -1
diff -urN linux-2.4.17/fs/autofs4/root.c linux-2.4.17-dcache_rcu-2/fs/autofs4/root.c
@@ -403,7 +403,7 @@
 		spin_unlock(&dcache_lock);
 		return -ENOTEMPTY;
 	}
-	list_del_init(&dentry->d_hash);
+	dentry_unhash(dentry);
 	spin_unlock(&dcache_lock);
 
 	dput(ino->dentry);
fs/coda/dir.c +2 -2
diff -urN linux-2.4.17/fs/coda/dir.c linux-2.4.17-dcache_rcu-2/fs/coda/dir.c
@@ -464,7 +464,7 @@
         CDEBUG(D_INODE, "old: %s, (%d length), new: %s"
 	       "(%d length). old:d_count: %d, new:d_count: %d\n", 
 	       old_name, old_length, new_name, new_length,
-	       atomic_read(&old_dentry->d_count), atomic_read(&new_dentry->d_count));
+	       old_dentry->d_count, new_dentry->d_count);
 
         error = venus_rename(old_dir->i_sb, coda_i2f(old_dir), 
 			     coda_i2f(new_dir), old_length, new_length, 

@@ -666,7 +666,7 @@
 	if (cii->c_flags & C_FLUSH) 
 		coda_flag_inode_children(inode, C_FLUSH);
 
-	if (atomic_read(&de->d_count) > 1) {
+	if (de->d_count > 1) {
 		/* pretend it's valid, but don't change the flags */
 		CDEBUG(D_DOWNCALL, "BOOM for: ino %ld, %s\n",
 		       de->d_inode->i_ino, coda_f2s(&cii->c_fid));
fs/coda/file.c +1 -1
diff -urN linux-2.4.17/fs/coda/file.c linux-2.4.17-dcache_rcu-2/fs/coda/file.c
@@ -105,7 +105,7 @@
 	coda_vfs_stat.open++;
 
 	CDEBUG(D_SPECIAL, "OPEN inode number: %ld, count %d, flags %o.\n", 
-	       f->f_dentry->d_inode->i_ino, atomic_read(&f->f_dentry->d_count), flags);
+	       f->f_dentry->d_inode->i_ino, f->f_dentry->d_count, flags);
 
 	error = venus_open(i->i_sb, coda_i2f(i), coda_flags, &fh); 
 	if (error || !fh) {
fs/coda/pioctl.c +1 -1
diff -urN linux-2.4.17/fs/coda/pioctl.c linux-2.4.17-dcache_rcu-2/fs/coda/pioctl.c
@@ -97,7 +97,7 @@
 
         CDEBUG(D_PIOCTL, "ioctl on inode %ld\n", target_inode->i_ino);
 	CDEBUG(D_DOWNCALL, "dput on ino: %ld, icount %d, dcount %d\n", target_inode->i_ino, 
-	       atomic_read(&target_inode->i_count), atomic_read(&nd.dentry->d_count));
+	       atomic_read(&target_inode->i_count), nd.dentry->d_count);
 	path_release(&nd);
         return error;
 }
fs/dcache.c +88 -63

338 lines not on this page · raw message

fs/hpfs/namei.c +1 -1
diff -urN linux-2.4.17/fs/hpfs/namei.c linux-2.4.17-dcache_rcu-2/fs/hpfs/namei.c
@@ -333,7 +333,7 @@
 		if (rep)
 			goto ret;
 		d_drop(dentry);
-		if (atomic_read(&dentry->d_count) > 1 ||
+		if (dentry->d_count > 1 ||
 		    permission(inode, MAY_WRITE) ||
 		    get_write_access(inode)) {
 			d_rehash(dentry);
fs/intermezzo/journal.c +1 -1
diff -urN linux-2.4.17/fs/intermezzo/journal.c linux-2.4.17-dcache_rcu-2/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);
fs/intermezzo/presto.c +1 -1
diff -urN linux-2.4.17/fs/intermezzo/presto.c linux-2.4.17-dcache_rcu-2/fs/intermezzo/presto.c
@@ -473,7 +473,7 @@
 
         // XXX this check makes no sense as d_count can change anytime.
         /* indicate if we were the only users while changing the flag */
-        if ( atomic_read(&dentry->d_count) > 1 )
+        if ( dentry->d_count > 1 )
                 error = -EBUSY;
 
 out:
fs/intermezzo/vfs.c +2 -2
diff -urN linux-2.4.17/fs/intermezzo/vfs.c linux-2.4.17-dcache_rcu-2/fs/intermezzo/vfs.c
@@ -1201,10 +1201,10 @@
 static void d_unhash(struct dentry *dentry)
 {
         dget(dentry);
-        switch (atomic_read(&dentry->d_count)) {
+        switch (dentry->d_count) {
         default:
                 shrink_dcache_parent(dentry);
-                if (atomic_read(&dentry->d_count) != 2)
+                if (dentry->d_count != 2)
                         break;
         case 2:
                 d_drop(dentry);
fs/locks.c +1 -1
diff -urN linux-2.4.17/fs/locks.c linux-2.4.17-dcache_rcu-2/fs/locks.c
@@ -1236,7 +1236,7 @@
 	 * FIXME: What about F_RDLCK and files open for writing?
 	 */
 	if ((arg == F_WRLCK)
-	    && ((atomic_read(&dentry->d_count) > 1)
+	    && ((dentry->d_count > 1)
 		|| (atomic_read(&inode->i_count) > 1)))
 		return -EAGAIN;
fs/namei.c +2 -2
diff -urN linux-2.4.17/fs/namei.c linux-2.4.17-dcache_rcu-2/fs/namei.c
@@ -1354,10 +1354,10 @@
 static void d_unhash(struct dentry *dentry)
 {
 	dget(dentry);
-	switch (atomic_read(&dentry->d_count)) {
+	switch (dentry->d_count) {
 	default:
 		shrink_dcache_parent(dentry);
-		if (atomic_read(&dentry->d_count) != 2)
+		if (dentry->d_count != 2)
 			break;
 	case 2:
 		d_drop(dentry);
fs/namespace.c +1 -1
diff -urN linux-2.4.17/fs/namespace.c linux-2.4.17-dcache_rcu-2/fs/namespace.c
@@ -1002,7 +1002,7 @@
 #if 1
 	shrink_dcache();
 	printk("change_root: old root has d_count=%d\n", 
-	       atomic_read(&old_rootmnt->mnt_root->d_count));
+	       old_rootmnt->mnt_root->d_count);
 #endif
 	mount_devfs_fs ();
 	/*
fs/nfs/dir.c +9 -9
diff -urN linux-2.4.17/fs/nfs/dir.c linux-2.4.17-dcache_rcu-2/fs/nfs/dir.c
@@ -754,9 +754,9 @@
 
 	dfprintk(VFS, "NFS: silly-rename(%s/%s, ct=%d)\n",
 		dentry->d_parent->d_name.name, dentry->d_name.name, 
-		atomic_read(&dentry->d_count));
+		dentry->d_count);
 
-	if (atomic_read(&dentry->d_count) == 1)
+	if (dentry->d_count == 1)
 		goto out;  /* No need to silly rename. */
 
 

@@ -833,11 +833,11 @@
 		d_drop(dentry);
 		rehash = 1;
 	}
-	if (atomic_read(&dentry->d_count) > 1) {
+	if (dentry->d_count > 1) {
 #ifdef NFS_PARANOIA
 		printk("nfs_safe_remove: %s/%s busy, d_count=%d\n",
 			dentry->d_parent->d_name.name, dentry->d_name.name,
-			atomic_read(&dentry->d_count));
+			dentry->d_count);
 #endif
 		goto out;
 	}

@@ -1005,7 +1005,7 @@
 	dfprintk(VFS, "NFS: rename(%s/%s -> %s/%s, ct=%d)\n",
 		 old_dentry->d_parent->d_name.name, old_dentry->d_name.name,
 		 new_dentry->d_parent->d_name.name, new_dentry->d_name.name,
-		 atomic_read(&new_dentry->d_count));
+		 new_dentry->d_count);
 
 	/*
 	 * First check whether the target is busy ... we can't

@@ -1019,7 +1019,7 @@
 		goto go_ahead;
 	if (S_ISDIR(new_inode->i_mode))
 		goto out;
-	else if (atomic_read(&new_dentry->d_count) > 1) {
+	else if (new_dentry->d_count > 1) {
 		int err;
 		/* copy the target dentry's name */
 		dentry = d_alloc(new_dentry->d_parent,

@@ -1037,12 +1037,12 @@
 		}
 
 		/* dentry still busy? */
-		if (atomic_read(&new_dentry->d_count) > 1) {
+		if (new_dentry->d_count > 1) {
 #ifdef NFS_PARANOIA
 			printk("nfs_rename: target %s/%s busy, d_count=%d\n",
 			       new_dentry->d_parent->d_name.name,
 			       new_dentry->d_name.name,
-			       atomic_read(&new_dentry->d_count));
+			       new_dentry->d_count);
 #endif
 			goto out;
 		}

@@ -1052,7 +1052,7 @@
 	/*
 	 * ... prune child dentries and writebacks if needed.
 	 */
-	if (atomic_read(&old_dentry->d_count) > 1) {
+	if (old_dentry->d_count > 1) {
 		nfs_wb_all(old_inode);
 		shrink_dcache_parent(old_dentry);
 	}
fs/nfsd/nfsfh.c +1 -1
diff -urN linux-2.4.17/fs/nfsd/nfsfh.c linux-2.4.17-dcache_rcu-2/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);
fs/nfsd/vfs.c +3 -3
diff -urN linux-2.4.17/fs/nfsd/vfs.c linux-2.4.17-dcache_rcu-2/fs/nfsd/vfs.c
@@ -1280,8 +1280,8 @@
 
 #ifdef MSNFS
 	if ((ffhp->fh_export->ex_flags & NFSEXP_MSNFS) &&
-		((atomic_read(&odentry->d_count) > 1)
-		 || (atomic_read(&ndentry->d_count) > 1))) {
+		((odentry->d_count > 1)
+		 || (ndentry->d_count > 1))) {
 			err = nfserr_perm;
 	} else
 #endif

@@ -1348,7 +1348,7 @@
 	if (type != S_IFDIR) { /* It's UNLINK */
 #ifdef MSNFS
 		if ((fhp->fh_export->ex_flags & NFSEXP_MSNFS) &&
-			(atomic_read(&rdentry->d_count) > 1)) {
+			(rdentry->d_count > 1)) {
 			err = nfserr_perm;
 		} else
 #endif
fs/readdir.c +1 -1
diff -urN linux-2.4.17/fs/readdir.c linux-2.4.17-dcache_rcu-2/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;
include/linux/dcache.h +64 -34

159 lines not on this page · raw message

Signature · 5 lines
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