dcache_rcu

Hello Viro,

Please consider forwarding the following patch ito Linus for dcache lookup using Read Copy Update. The patch has been there in -mm kernel since 2.5.37-mm1. The patch is stable. A couple of bugs reported are solved. It helps a great deal on higher end SMP machines and there is no performance regression on UP and lower end SMP machines as seen in Dipankar's kernbench numbers.

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

Regards,
Maneesh

diff -urN linux-2.5.44-base/drivers/usb/core/inode.c linux-2.5.44-dc12/drivers/usb/core/inode.c
@@ -254,7 +254,7 @@
 		if (atomic_read(&dentry->d_count) != 2)
 			break;
 	case 2:
-		list_del_init(&dentry->d_hash);
+		__d_drop(dentry);
 	}
 	spin_unlock(&dcache_lock);
 }

diff -urN linux-2.5.44-base/fs/autofs4/root.c linux-2.5.44-dc12/fs/autofs4/root.c
@@ -418,7 +418,7 @@
 		unlock_kernel();
 		return -ENOTEMPTY;
 	}
-	list_del_init(&dentry->d_hash);
+	__d_drop(dentry);
 	spin_unlock(&dcache_lock);
 
 	dput(ino->dentry);

diff -urN linux-2.5.44-base/fs/exec.c linux-2.5.44-dc12/fs/exec.c
@@ -502,9 +502,9 @@
 
 	if (proc_dentry) {
 		spin_lock(&dcache_lock);
-		if (!list_empty(&proc_dentry->d_hash)) {
+		if (!d_unhashed(proc_dentry)) {
 			dget_locked(proc_dentry);
-			list_del_init(&proc_dentry->d_hash);
+			__d_drop(proc_dentry);
 		} else
 			proc_dentry = NULL;
 		spin_unlock(&dcache_lock);

diff -urN linux-2.5.44-base/fs/intermezzo/journal.c linux-2.5.44-dc12/fs/intermezzo/journal.c
@@ -261,7 +261,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);

@@ -1518,7 +1518,7 @@
         }
 
         if (!dentry->d_inode || (dentry->d_inode->i_nlink == 0) 
-            || ((dentry->d_parent != dentry) && list_empty(&dentry->d_hash))) {
+            || ((dentry->d_parent != dentry) && d_unhashed(dentry))) {
                 EXIT;
                 return 0;
         }

@@ -2129,7 +2129,7 @@
         }
 
         if (!dentry->d_inode || (dentry->d_inode->i_nlink == 0) 
-            || ((dentry->d_parent != dentry) && list_empty(&dentry->d_hash))) {
+            || ((dentry->d_parent != dentry) && d_unhashed(dentry))) {
                 EXIT;
                 return 0;
         }

@@ -2391,7 +2391,7 @@
         }
 
         if (!dentry->d_inode || (dentry->d_inode->i_nlink == 0) 
-            || ((dentry->d_parent != dentry) && list_empty(&dentry->d_hash))) {
+            || ((dentry->d_parent != dentry) && d_unhashed(dentry))) {
                 EXIT;
                 return 0;
         }

diff -urN linux-2.5.44-base/fs/libfs.c linux-2.5.44-dc12/fs/libfs.c
@@ -70,7 +70,7 @@
 			while (n && p != &file->f_dentry->d_subdirs) {
 				struct dentry *next;
 				next = list_entry(p, struct dentry, d_child);
-				if (!list_empty(&next->d_hash) && next->d_inode)
+				if (!d_unhashed(next) && next->d_inode)
 					n--;
 				p = p->next;
 			}

@@ -127,7 +127,7 @@
 			for (p=q->next; p != &dentry->d_subdirs; p=p->next) {
 				struct dentry *next;
 				next = list_entry(p, struct dentry, d_child);
-				if (list_empty(&next->d_hash) || !next->d_inode)
+				if (d_unhashed(next) || !next->d_inode)
 					continue;
 
 				spin_unlock(&dcache_lock);

diff -urN linux-2.5.44-base/fs/nfs/dir.c linux-2.5.44-dc12/fs/nfs/dir.c
@@ -1001,7 +1001,7 @@
 		return error;
 	}
 	if (!d_unhashed(dentry)) {
-		list_del_init(&dentry->d_hash);
+		__d_drop(dentry);
 		need_rehash = 1;
 	}
 	spin_unlock(&dcache_lock);

diff -urN linux-2.5.44-base/include/linux/dcache.h linux-2.5.44-dc12/include/linux/dcache.h
@@ -7,6 +7,7 @@
 #include <linux/mount.h>
 #include <linux/list.h>
 #include <linux/spinlock.h>
+#include <linux/rcupdate.h>
 #include <asm/page.h>			/* for BUG() */
 
 /*

@@ -70,11 +71,13 @@
  
 struct dentry {
 	atomic_t d_count;
+	unsigned long d_vfs_flags;	/* moved here to be on same cacheline */
+	spinlock_t d_lock;		/* per dentry lock */
 	unsigned int d_flags;
 	struct inode  * d_inode;	/* Where the name belongs to - NULL is negative */
 	struct dentry * d_parent;	/* parent directory */
 	struct list_head d_hash;	/* lookup hash list */
-	struct list_head d_lru;		/* d_count = 0 LRU list */
+	struct list_head d_lru;		/* LRU list */
 	struct list_head d_child;	/* child of parent list */
 	struct list_head d_subdirs;	/* our children */
 	struct list_head d_alias;	/* inode alias list */

@@ -83,8 +86,8 @@
 	unsigned long d_time;		/* used by d_revalidate */
 	struct dentry_operations  *d_op;
 	struct super_block * d_sb;	/* The root of the dentry tree */
-	unsigned long d_vfs_flags;
 	void * d_fsdata;		/* fs-specific data */
+	struct rcu_head d_rcu;
 	unsigned char d_iname[DNAME_INLINE_LEN]; /* small names */
 	struct dcookie_struct * d_cookie; /* cookie, if any */
 };

@@ -135,6 +138,7 @@
       */
 
 #define DCACHE_REFERENCED	0x0008  /* Recently used, don't discard. */
+#define DCACHE_UNHASHED		0x0010	
 
 extern spinlock_t dcache_lock;
 extern rwlock_t dparent_lock;

@@ -156,10 +160,16 @@
  * timeouts or autofs deletes).
  */
 
+static __inline__ void __d_drop(struct dentry * dentry)
+{
+	dentry->d_vfs_flags |= DCACHE_UNHASHED;
+	list_del_rcu(&dentry->d_hash);
+}
+
 static __inline__ void d_drop(struct dentry * dentry)
 {
 	spin_lock(&dcache_lock);
-	list_del_init(&dentry->d_hash);
+ 	__d_drop(dentry);
 	spin_unlock(&dcache_lock);
 }
 

@@ -246,9 +256,8 @@
 static __inline__ struct dentry * dget(struct dentry *dentry)
 {
 	if (dentry) {
-		if (!atomic_read(&dentry->d_count))
-			BUG();
 		atomic_inc(&dentry->d_count);
+		dentry->d_vfs_flags |= DCACHE_REFERENCED;
 	}
 	return dentry;
 }

@@ -264,7 +273,7 @@
  
 static __inline__ int d_unhashed(struct dentry *dentry)
 {
-	return list_empty(&dentry->d_hash);
+	return (dentry->d_vfs_flags & DCACHE_UNHASHED);
 }
 
 extern void dput(struct dentry *);

diff -urN linux-2.5.44-base/include/linux/fs_struct.h linux-2.5.44-dc12/include/linux/fs_struct.h
@@ -35,12 +35,10 @@
 	struct dentry *old_root;
 	struct vfsmount *old_rootmnt;
 	write_lock(&fs->lock);
-	spin_lock(&dcache_lock);
 	old_root = fs->root;
 	old_rootmnt = fs->rootmnt;
 	fs->rootmnt = mntget(mnt);
 	fs->root = dget(dentry);
-	spin_unlock(&dcache_lock);
 	write_unlock(&fs->lock);
 	if (old_root) {
 		dput(old_root);

@@ -60,12 +58,10 @@
 	struct dentry *old_pwd;
 	struct vfsmount *old_pwdmnt;
 	write_lock(&fs->lock);
-	spin_lock(&dcache_lock);
 	old_pwd = fs->pwd;
 	old_pwdmnt = fs->pwdmnt;
 	fs->pwdmnt = mntget(mnt);
 	fs->pwd = dget(dentry);
-	spin_unlock(&dcache_lock);
 	write_unlock(&fs->lock);
 	if (old_pwd) {
 		dput(old_pwd);

diff -urN linux-2.5.44-base/include/linux/namei.h linux-2.5.44-dc12/include/linux/namei.h
@@ -11,8 +11,6 @@
 	struct qstr	last;
 	unsigned int	flags;
 	int		last_type;
-	struct dentry	*old_dentry;
-	struct vfsmount	*old_mnt;
 };
 
 /*

diff -urN linux-2.5.44-base/kernel/exit.c linux-2.5.44-dc12/kernel/exit.c
@@ -46,9 +46,9 @@
 	proc_dentry = p->proc_dentry;
 	if (unlikely(proc_dentry != NULL)) {
 		spin_lock(&dcache_lock);
-		if (!list_empty(&proc_dentry->d_hash)) {
+		if (!d_unhashed(proc_dentry)) {
 			dget_locked(proc_dentry);
-			list_del_init(&proc_dentry->d_hash);
+			__d_drop(proc_dentry);
 		} else
 			proc_dentry = NULL;
 		spin_unlock(&dcache_lock);

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

Anton (Blanchard) did some benchmarking with this
in a 24-way ppc64 box and the results showed why we need this patch. Here are some performace comparisons based on a multi-user benchmark that Anton ran with vanilla 2.5.40 and 2.5.40-mm.

http://lse.sourceforge.net/locking/dcache/summary.png

base = 2.5.40
base-nops = 2.5.40 but ps command in benchmark scripts commented out mm = 2.5.40-mm
mm-nops = 2.5.40-mm but ps command in benchmark scripts commented out

Here is a profile output snippet of base and mm runs at 200 scripts -

base :

Hits Percentage Function
------------------------
75185 100.00 total
11215 14.92 path_lookup
8578 11.41 atomic_dec_and_lock
5763 7.67 do_lookup
5745 7.64 proc_pid_readlink
4344 5.78 page_remove_rmap
2144 2.85 page_add_rmap
1587 2.11 link_path_walk
1531 2.04 proc_check_root
1461 1.94 save_remaining_regs
1345 1.79 inode_change_ok
1236 1.64 ext2_free_blocks
1215 1.62 ext2_new_block
1067 1.42 d_lookup
1053 1.40 number
907 1.21 release_pages

mm :

Hits Percentage Function
62369 100.00 total
5802 9.30 page_remove_rmap
4092 6.56 atomic_dec_and_lock
3887 6.23 proc_pid_readlink
3207 5.14 follow_mount
2979 4.78 page_add_rmap
2066 3.31 save_remaining_regs
1856 2.98 d_lookup
1629 2.61 number
1235 1.98 release_pages
1168 1.87 pSeries_flush_hash_range
1154 1.85 do_page_fault
1026 1.65 copy_page
1009 1.62 path_lookup

Thanks

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

I'm going to need some help understanding what's going on in there. I assume the test is SDET (there, I said it), which simulates lots of developers doing developer things on a multiuser machine. Lots of compiling, groffing, etc.

Why does the removal of `ps' from the test script make such a huge difference? That's silly, and we should fix it.

And it appears that dcache-rcu made a ~10% difference on a 24-way PPC64, yes? That is nice, and perhaps we should take that, but it is not a tremendous speedup.

Thanks.

I have uploaded the profiles from Anton's benchmark runs -

http://lse.sourceforge.net/locking/dcache/results/2.5.40/200-base.html
http://lse.sourceforge.net/locking/dcache/results/2.5.40/200-base-nops.html
http://lse.sourceforge.net/locking/dcache/results/2.5.40/200-mm.html
http://lse.sourceforge.net/locking/dcache/results/2.5.40/200-mm-nops.html

A quick comparison of base and base-nops profiles show this -

base :

Hits Percentage Function
75185 100.00 total
11215 14.92 path_lookup <1.html>
8578 11.41 atomic_dec_and_lock <2.html>
5763 7.67 do_lookup <3.html>
5745 7.64 proc_pid_readlink <4.html>
4344 5.78 page_remove_rmap <5.html>
2144 2.85 page_add_rmap <6.html>
1587 2.11 link_path_walk <7.html>
1531 2.04 proc_check_root <8.html>
1461 1.94 save_remaining_regs <9.html>
1345 1.79 inode_change_ok <10.html>
1236 1.64 ext2_free_blocks <11.html>
1215 1.62 ext2_new_block <12.html>
1067 1.42 d_lookup <13.html>

base-no-ps :

Hits Percentage Function
50895 100.00 total
8222 16.15 page_remove_rmap <1.html>
3837 7.54 page_add_rmap <2.html>
2222 4.37 save_remaining_regs <3.html>
1618 3.18 release_pages <4.html>
1533 3.01 pSeries_flush_hash_range <5.html>
1446 2.84 do_page_fault <6.html>
1343 2.64 find_get_page <7.html>
1273 2.50 copy_page <8.html>
1228 2.41 copy_page_range <9.html>
1186 2.33 path_lookup <10.html>
1186 2.33 pSeries_insert_hpte <11.html>
1171 2.30 atomic_dec_and_lock <12.html>
1152 2.26 zap_pte_range <13.html>
841 1.65 do_generic_file_read <14.html>

Clearly dcache_lock is the killer when 'ps' command is used in the benchmark. My guess (without looking at 'ps' code) is that it has to open/close a lot of files in /proc and that increases the number of acquisitions of dcache_lock. Increased # of acquisition add to cache line bouncing and contention.

I should add that this is a general trend we see in all workloads that do a lot of open/closes and so much so that performance is very sensitive to how close to / your application's working directory is. You would get much better system time if you compile a kernel in /linux as compared to say /home/fs01/users/akpm/kernel/linux ;-)

Hmm.. based on Anton's graph it looked more like ~25% difference for 60 or more scripts. At 200 scripts it is ~27.6%. Without the ps command, it seems more like ~4%.

Thanks
Dipankar

Strace it - IIRC it does 5 opens per PID. Vomit.

M.

I just did, had the same reaction. This is ugly.

It opens stat, statm, status, cmdline and environ apparently regardless of what will be in the ouput. At least environ will fail on most pids if you aren't root, saving on some of the overhead. It compunds this by doing so for every pid even if you have explicitly requested only one pid by number.

Clearly ps could do with a cleanup. There is no reason to
read environ if it wasn't asked for. Deciding which files
are needed based on the command line options would be a start.

I'm thinking that ps, top and company are good reasons to make an exception of one value per file in proc. Clearly open+read+close of 3-5 "files" each extracting data from task_struct isn't more efficient than one "file" that generates the needed data one field per line.

Don't get me wrong. I believe in the one field per file rule but ps &co are the exception that proves (tests) the rule. Especially on the heavily laden systems with tens of thousands of tasks. We could do with a something between /dev/kmem and five files per pid.

________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		[email protected]

		Remember Cernan and Schmitt

I think it's pretty trivial to make /proc/<pid>/psinfo, which dumps the garbage from all five files in one place. Which makes it 5 times better, but it still sucks.

I had a very brief think about this at the weekend, seeing if I could make a big melting pot /proc/psinfo file that did seqfile and read everything out in one go, using seq_file internally to interate over the tasklist. The most obvious problem that sprung to mind seems to be the tasklist locking - you obviously can't just hold a lock over the whole thing. As I know very little about that, I'll let someone else suggest how to do this, but I'm prepared to do the grunt work of implementing it if need be.

M.

You could take a more radical approach. Since the goal of such a psinfo file would be to accelerate access to information that's already available elsewhere, you can do away with many of the niceties of procfs, e.g.

- no need to be human-readable (e.g. binary or hex dump may make sense in this case)
- may use other operations than just open and read (e.g. do an initial write to select what should be read)
- you may cache previous responses and only output deltas (not sure if this is useful - all you'd safe is the actual copy to user space)

Actually, I think attempting to just make it brutally efficient, no matter how much nastiness you amass doing that, might be good approach for a first version. Then, if people are digusted, you can make things nicer, and keep track of how much performance you're losing.

Example:

First write says "pid,comm". Internally, this gets translated to 0x8c+0x04, 0x2ee+0x10 (offset+length). Next read returns "pid 4,comm 16" (include the name, so you can indicate fields the kernel doesn't recognize). Then, kmalloc 20*tasks bytes, lock, copy the fields from struct task_struct, unlock, let the stuff be read by user space, kfree. Adjacent fields can be optimized to single byte strings at setup time.

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         [email protected] /
/_http://www.almesberger.net/____________________________________________/

Hehe. You just reinvented my old /dev/ps driver. :)

http://www.busybox.net/cgi-bin/cvsweb/busybox/examples/kernel-patches/devps.patch.9_25_2000?rev=1.2&content-type=text/vnd.viewcvs-markup

This is what Linus has to say on the subject:

I do dislike /dev/ps mightily. If the problem is that /proc is too large, then the right solution is to just clean up /proc. Which is getting done. And yes, /proc will be larger than /dev/ps, but I still find that preferable to having two incompatible ways to do the same thing.

-Erik

--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--

Indeed, sounds much more like a /dev thing than a /proc thing at this point ;-)

Ummm ... how do we make /proc smaller than 1 file to open per PID? It's pretty easy to get it down that far. But it still sucks.

Well it can't be any worse than the current crap. At least it'd stand a chance in hell of scaling a little bit. So I took a very quick look ... what syscalls are you reduced to per pid, one ioctl and one read?

M.

Oh, yes it can. Easily.
* device is not network-transparent - even in principle
* restricting data access would be harder - welcome to suid or
sgid country
* real killer: you think Albert would fail to produce equally
crappy code and equally crappy behaviour? Yeah, right.

Is that really a major issue for ps?

I can live with that level of pain if my benchmark doesn't get driven into the wall by the tools that are meant to be montoring it ...

I'm sure there are bigger rocks to be thrown at it as well, and ugly critters to be found under those rocks, but I don't see anything insurmountable here yet. Whereas opening billions of files is just unworkable.

Better still, you seem like an excellent candidate to propose a good design that's efficient and workable?

Heh ;-)
A hostile takeover might suffice here, if necessary ...

M.

Well I think Rik and I can handle it in our tree :)

But I agree - I do not care much for this /dev idea either.

Robert Love

As I implemented it, it was one ioctl per pid... Of course it could be easily modified to be one syscall, one read from the /dev/ps char device, or similar...

-Erik

--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--

Hmm, you still need 2+#pids operations, while my approach could essentially do everything in a single read. Besides, many people don't exactly love ioctls.

Furthermore, you'd need to version your big struct pid_info, while my approach wouldn't have problems if fields are added or removed (only if their content changes).

Two advantages of your approach are that the amount of data cached in the kernel is limited to max(sizeof(pid_t)*#pids, sizeof(struct pid_info)), and that you do less work under tasklist_lock.

Hmm yes, so he might not like my /proc/grab-taskdata-FAST either :)

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         [email protected] /
/_http://www.almesberger.net/____________________________________________/

And i'd still keep environ seperate. I'm inclined to think ps should never have presented it in the first place. This is the direction i (for what it's worth) favor.

Yep, can't hold the lock across syscalls. That would be quite a bit of data to hold in a per fd buffer. Think of the big iron with tons of processes.

The other way i could see this working is to present it as a sparse file. ps (or whatever) would first get a list of pids then iterate over them using lseek to set the file offset to pid * CONSTANT_SIZE and read would return something smaller than CONSTANT_SIZE bytes. If the pid no longer exists return 0.

I really hate this idea. It stinks almost as much as /dev/kmem.

________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		[email protected]

		Remember Cernan and Schmitt

If it doesn't need it then sure, otherwise just dump whatever it needs in there. The seperate files would still be there too.

I *have* the big iron with tons of processes ;-) That's why I care ...

Well if we want to be gross and efficient, we could just compile a kmem-diving dynamic library with every kernel compile and stick it in /boot or somewhere. Mildly less extreme is a flat index file for the data you need a la System.map. Then just open /dev/kmem and grab what you want. Walking the tasklist with no locking would be an interesting challenge, but probably not insurmountable. That's how things like ps always used to work IIRC.

M.

[email protected] (Martin J. Bligh) wrote on 04.11.02 in <1118170000.1036458859@flay>:

Well, one thing i to make certain you can actually do it with one or two system calls. Say, one system call to figure out how big a buffer is necessary (essentially, #tasks*size), then one read with a suitably-sized buffer. Then have a loop in the kernel that drops the lock as often as necessary, and otherwise puts it all in the buffer in one go. (If the #tasks grows too fast so it overruns the buffer even with some slack given in advance, tough, have a useful return code to indicate that and let ps retry.)

I briefly thought about mmap, but I don't think that actually buys anything.

MfG Kai

Once again, reminds me of my /dev/ps driver, which had the following ioctls:

#define DEVPS_GET_NUM_PIDS     0xeba1 /* Get a list of all PIDs */ 
#define DEVPS_GET_PID_LIST     0xeba2 /* Get a list of all PIDs */ 
#define DEVPS_GET_PID_INFO     0xeba3 /* Get info about a specific PID */
#define DEVPS_GET_CURRENT_PID  0xeba4 /* Get the current PID */

So a user spave ps app would call DEVPS_GET_NUM_PIDS to find out how many processes there are, then it would allocate some memory (and would allocate a some extra just in case some new processes were to start up, the kernel would truncate things if we gave it too little space) . Then ps would grab the pid list by calling the DEVPS_GET_PID_LIST ioctl, and then for each item in the list it would call DEVPS_GET_PID_INFO. Assuming that call was successful, ps would print out a line of output and move on to the next pid in the list.

The idea need not be implemented without using ioctl and without using binary structures (which were the things Linus objected to)

The same thing could be easily done using flat ascii...

-Erik

--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--

I'm not sure why people are trying to make pigs fly, but if you really need in-depth information regarding a process or a set of processes, you should be looking at something that's been designed from the ground up to actually carry this weight, which is exactly what LTT is about. Using this approach, all the accounting gets to be done in user-space. It's like using "top -q" without the actual disadvantage of killing your system.

Karim

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================