Skip to contentSkip to conversation

2.5.5-dj2 - Fast Walk Dcache to Decrease Cacheline Bouncing

PATCH In review Hanna Linder 2 participants 3 messages Mar 5, 2002

Subsystems (2)
VFS exec and binfmt
lore
Share & tools
lore

Hanna Linder

author
#0 lore raw

PATCH 1/1 2.5.5-dj2 - Fast Walk Dcache to Decrease Cacheline Bouncing

I would like you to consider this patch for inclusion in 2.5.6.

What it does:

The simple part combines path_init and path_walk into one function path_lookup. Which was a simple cleanup of the code. The more complex part is changing link_path_walk and cached_lookup to hold the dcache_lock instead of incrementing the d_count reference counter while walking the path as long as the desired dentry's are found in the dcache. Dave Olien wrote permission_exec_lite. These ideas came from Al Viro to decrease cacheline bouncing.

Performance benefits running dbench with 16 clients 10 times on an 8-way SMP:

On 2.5.5-dj2 it
-reduces TOTAL system spinlock contention from 8.7 to 6.5 -reduces TOTAL system MAX HOLD time from 37ms to 17ms -reduces lru_list_lock spinning from 31.4% to 5.7% -reduces lru_list_lock contention from 38.3% to 15.4%

Testing:

It compiles and boots and runs as well or better as the clean 2.5.5-dj2 kernel. I have run it on my T21 laptop and my 8-way SMP system.

Please let me know if there are any changes I can make or tests I can run to increase the chance of it being accepted.

Thanks.

Hanna Linder ([email protected])
IBM Linux Technology Center

-----------

fs/dcache.c +11 -3
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/fs/dcache.c linux-2.5.5-fastwalk/fs/dcache.c
@@ -705,13 +705,23 @@
  
 struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
 {
+	struct dentry *dentry = NULL;
+
+	spin_lock(&dcache_lock);
+	dentry = __d_lookup(parent,name);
+	spin_unlock(&dcache_lock);
+	return dentry;
+}
+
+struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)  
+{
+
 	unsigned int len = name->len;
 	unsigned int hash = name->hash;
 	const unsigned char *str = name->name;
 	struct list_head *head = d_hash(parent,hash);
 	struct list_head *tmp;
 
-	spin_lock(&dcache_lock);
 	tmp = head->next;
 	for (;;) {
 		struct dentry * dentry = list_entry(tmp, struct dentry, d_hash);

@@ -733,10 +743,8 @@
 		}
 		__dget_locked(dentry);
 		dentry->d_vfs_flags |= DCACHE_REFERENCED;
-		spin_unlock(&dcache_lock);
 		return dentry;
 	}
-	spin_unlock(&dcache_lock);
 	return NULL;
 }
fs/exec.c +1 -2
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/fs/exec.c linux-2.5.5-fastwalk/fs/exec.c
@@ -347,8 +347,7 @@
 	struct file *file;
 	int err = 0;
 
-	if (path_init(name, LOOKUP_FOLLOW|LOOKUP_POSITIVE, &nd))
-		err = path_walk(name, &nd);
+	err = path_lookup(name, LOOKUP_FOLLOW|LOOKUP_POSITIVE, &nd);
 	file = ERR_PTR(err);
 	if (!err) {
 		inode = nd.dentry->d_inode;
fs/namei.c +123 -31

299 lines not on this page · raw message

fs/namespace.c +6 -12
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/fs/namespace.c linux-2.5.5-fastwalk/fs/namespace.c
@@ -368,8 +368,7 @@
 	if (IS_ERR(kname))
 		goto out;
 	retval = 0;
-	if (path_init(kname, LOOKUP_POSITIVE|LOOKUP_FOLLOW, &nd))
-		retval = path_walk(kname, &nd);
+	retval = path_lookup(kname, LOOKUP_POSITIVE|LOOKUP_FOLLOW, &nd); 
 	putname(kname);
 	if (retval)
 		goto out;

@@ -497,8 +496,7 @@
 		return err;
 	if (!old_name || !*old_name)
 		return -EINVAL;
-	if (path_init(old_name, LOOKUP_POSITIVE|LOOKUP_FOLLOW, &old_nd))
-		err = path_walk(old_name, &old_nd);
+	err = path_lookup(old_name, LOOKUP_POSITIVE|LOOKUP_FOLLOW, &old_nd);
 	if (err)
 		return err;
 

@@ -564,8 +562,7 @@
 		return -EPERM;
 	if (!old_name || !*old_name)
 		return -EINVAL;
-	if (path_init(old_name, LOOKUP_POSITIVE|LOOKUP_FOLLOW, &old_nd))
-		err = path_walk(old_name, &old_nd);
+	err = path_lookup(old_name, LOOKUP_POSITIVE|LOOKUP_FOLLOW, &old_nd);
 	if (err)
 		return err;
 

@@ -731,8 +728,7 @@
 	flags &= ~(MS_NOSUID|MS_NOEXEC|MS_NODEV);
 
 	/* ... and get the mountpoint */
-	if (path_init(dir_name, LOOKUP_FOLLOW|LOOKUP_POSITIVE, &nd))
-		retval = path_walk(dir_name, &nd);
+	retval = path_lookup(dir_name, LOOKUP_FOLLOW|LOOKUP_POSITIVE, &nd);
 	if (retval)
 		return retval;
 

@@ -924,8 +920,7 @@
 	if (IS_ERR(name))
 		goto out0;
 	error = 0;
-	if (path_init(name, LOOKUP_POSITIVE|LOOKUP_FOLLOW|LOOKUP_DIRECTORY, &new_nd))
-		error = path_walk(name, &new_nd);
+	error = path_lookup(name, LOOKUP_POSITIVE|LOOKUP_FOLLOW|LOOKUP_DIRECTORY, &new_nd);
 	putname(name);
 	if (error)
 		goto out0;

@@ -938,8 +933,7 @@
 	if (IS_ERR(name))
 		goto out1;
 	error = 0;
-	if (path_init(name, LOOKUP_POSITIVE|LOOKUP_FOLLOW|LOOKUP_DIRECTORY, &old_nd))
-		error = path_walk(name, &old_nd);
+	error = path_lookup(name, LOOKUP_POSITIVE|LOOKUP_FOLLOW|LOOKUP_DIRECTORY, &old_nd);
 	putname(name);
 	if (error)
 		goto out1;
fs/open.c +2 -4
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/fs/open.c linux-2.5.5-fastwalk/fs/open.c
@@ -368,8 +368,7 @@
 		goto out;
 
 	error = 0;
-	if (path_init(name,LOOKUP_POSITIVE|LOOKUP_FOLLOW|LOOKUP_DIRECTORY,&nd))
-		error = path_walk(name, &nd);
+	error = path_lookup(name,LOOKUP_POSITIVE|LOOKUP_FOLLOW|LOOKUP_DIRECTORY,&nd);
 	putname(name);
 	if (error)
 		goto out;

@@ -427,9 +426,8 @@
 	if (IS_ERR(name))
 		goto out;
 
-	path_init(name, LOOKUP_POSITIVE | LOOKUP_FOLLOW |
+	error = path_lookup(name, LOOKUP_POSITIVE | LOOKUP_FOLLOW |
 		      LOOKUP_DIRECTORY | LOOKUP_NOALT, &nd);
-	error = path_walk(name, &nd);	
 	putname(name);
 	if (error)
 		goto out;
fs/super.c +1 -2
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/fs/super.c linux-2.5.5-fastwalk/fs/super.c
@@ -710,8 +710,7 @@
 	/* What device it is? */
 	if (!dev_name || !*dev_name)
 		return ERR_PTR(-EINVAL);
-	if (path_init(dev_name, LOOKUP_FOLLOW|LOOKUP_POSITIVE, &nd))
-		error = path_walk(dev_name, &nd);
+	error = path_lookup(dev_name, LOOKUP_FOLLOW|LOOKUP_POSITIVE, &nd);
 	if (error)
 		return ERR_PTR(error);
 	inode = nd.dentry->d_inode;
include/linux/dcache.h +1 -0
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/include/linux/dcache.h linux-2.5.5-fastwalk/include/linux/dcache.h
@@ -221,6 +221,7 @@
 
 /* appendix may either be NULL or be used for transname suffixes */
 extern struct dentry * d_lookup(struct dentry *, struct qstr *);
+extern struct dentry * __d_lookup(struct dentry *, struct qstr *);
 
 /* validate "insecure" dentry pointer */
 extern int d_validate(struct dentry *, struct dentry *);
include/linux/fs.h +4 -0
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/include/linux/fs.h linux-2.5.5-fastwalk/include/linux/fs.h
@@ -1271,6 +1271,7 @@
  *  - require a directory
  *  - ending slashes ok even for nonexistent files
  *  - internal "there are more path compnents" flag
+ *  - locked when lookup done with dcache_lock held
  */
 #define LOOKUP_FOLLOW		(1)
 #define LOOKUP_DIRECTORY	(2)

@@ -1278,6 +1279,8 @@
 #define LOOKUP_POSITIVE		(8)
 #define LOOKUP_PARENT		(16)
 #define LOOKUP_NOALT		(32)
+#define LOOKUP_LOCKED		(64)
+
 /*
  * Type of the last component on LOOKUP_PARENT
  */

@@ -1307,6 +1310,7 @@
 extern int FASTCALL(__user_walk(const char *, unsigned, struct nameidata *));
 extern int FASTCALL(path_init(const char *, unsigned, struct nameidata *));
 extern int FASTCALL(path_walk(const char *, struct nameidata *));
+extern int FASTCALL(path_lookup(const char *, unsigned, struct nameidata *));
 extern int FASTCALL(link_path_walk(const char *, struct nameidata *));
 extern void path_release(struct nameidata *);
 extern int follow_down(struct vfsmount **, struct dentry **);
kernel/ksyms.c +1 -0
diff -Nru --exclude-from=dontdiff linux-2.5.5-dj2/kernel/ksyms.c linux-2.5.5-fastwalk/kernel/ksyms.c
@@ -145,6 +145,7 @@
 EXPORT_SYMBOL(lookup_mnt);
 EXPORT_SYMBOL(path_init);
 EXPORT_SYMBOL(path_walk);
+EXPORT_SYMBOL(path_lookup);
 EXPORT_SYMBOL(path_release);
 EXPORT_SYMBOL(__user_walk);
 EXPORT_SYMBOL(lookup_one_len);
#1 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

"hanna" == Hanna Linder <[email protected]> writes:

Hi
hanna> --- linux-2.5.5-dj2/fs/dcache.c Mon Mar 4 15:56:20 2002
hanna> +++ linux-2.5.5-fastwalk/fs/dcache.c Fri Mar 1 16:21:40 2002
hanna> @@ -705,13 +705,23 @@

hanna> struct dentry * d_lookup(struct dentry * parent, struct qstr * name) hanna> {
hanna> + struct dentry *dentry = NULL;

Not needed.

hanna> +int path_lookup(const char *name, unsigned int flags, struct nameidata *nd) hanna> +{
hanna> + nd->last_type = LAST_ROOT; /* if there are only slashes... */
hanna> + nd->flags = flags;
hanna> + if (*name=='/'){
hanna> + read_lock(&current->fs->lock);
hanna> + if (current->fs->altroot && !(nd->flags & LOOKUP_NOALT)) {
hanna> + nd->mnt = mntget(current->fs->altrootmnt);
hanna> + nd->dentry = dget(current->fs->altroot);
hanna> + read_unlock(&current->fs->lock);
hanna> + if (__emul_lookup_dentry(name,nd))
hanna> + return 0;
hanna> + read_lock(&current->fs->lock);
hanna> + }
hanna> + spin_lock(&dcache_lock); /*to avoid cacheline bouncing with d_count*/
hanna> + nd->mnt = current->fs->rootmnt;
hanna> + nd->dentry = current->fs->root;
hanna> + read_unlock(&current->fs->lock);
hanna> + }
hanna> + else{
hanna> + read_lock(&current->fs->lock);
hanna> + spin_lock(&dcache_lock);
hanna> + nd->mnt = current->fs->pwdmnt;
hanna> + nd->dentry = current->fs->pwd;
hanna> + read_unlock(&current->fs->lock);
hanna> + }
hanna> + nd->flags |= LOOKUP_LOCKED;
hanna> + return (path_walk(name, nd));
hanna> +}
hanna> +

Would you mean retest if the speed is the same using lik the old code

(already static inline)
/* SMP-safe */
static inline int
walk_init_root(const char *name, struct nameidata *nd)

{
	read_lock(&current->fs->lock);
	if (current->fs->altroot && !(nd->flags & LOOKUP_NOALT)) {
		nd->mnt = mntget(current->fs->altrootmnt);
		nd->dentry = dget(current->fs->altroot);
		read_unlock(&current->fs->lock);
		if (__emul_lookup_dentry(name,nd))
			return 0;
		read_lock(&current->fs->lock);
	}
	nd->mnt = mntget(current->fs->rootmnt);
	nd->dentry = dget(current->fs->root);
	read_unlock(&current->fs->lock);
	return 1;
}

/* SMP-safe */
int path_lookup(const char *name, unsigned int flags, struct nameidata *nd)

{
	nd->last_type = LAST_ROOT; /* if there are only slashes... */
	nd->flags = flags;
	if (*name=='/')
		walk_init_root(name,nd);
        else {
        	read_lock(&current->fs->lock);
                nd->mnt = mntget(current->fs->pwdmnt);
                nd->dentry = dget(current->fs->pwd);
                read_unlock(&current->fs->lock);
        }
	nd->flags |= LOOKUP_LOCKED;
	return (path_walk(name, nd));
}

I think that it should not made difference, and code is IMHO, more readadble (and you don't duplicate walk_init_root).

Later, Juan.

Signature · 2 lines
In theory, practice and theory are the same, but in practice they 
are different -- Larry McVoy
author
#2 lore raw
Quoted 6 lines · --On Tuesday, March 05, 2002 04:30:00 +0100 Juan Quintela…

hanna> struct dentry * d_lookup(struct dentry * parent, struct qstr * name) hanna> {
hanna> + struct dentry *dentry = NULL;

Not needed.

Good catch. Changed.

Quoted 2 lines

Would you mean retest if the speed is the same using lik the old code

Any tests people would like to see that might increase the chance of it getting accepted.

Quoted 4 lines

I think that it should not made difference, and code is IMHO, more readadble (and you don't duplicate walk_init_root).

There is a difference. The reviewer of the first submission also missed it. path_lookup duplicates walk_init_root because mntget and dget are not called when the dcache_lock is held. So it is not an exact copy of walk_init_root.

The point of this is to find all the dentries in the path being walked already in the dcache (aka the easy lookups) without bumping the reference counter for every single dentry. On SMP this can lead to cacheline bouncing. When a dentry is not found in the cache then call mntget and dget followed by releasing the dcache_lock to continue. Al Viro came up with this idea, I have implemented it.

The lockmeter results and patch are here: http://lse.sf.net/locking

Hanna Linder ([email protected])
IBM Linux Technology Center