Skip to contentSkip to conversation

RCU'd vfsmounts

PATCH In review Al Viro 7 participants 20 messages Oct 3, 2013 – Oct 4, 2013 4 messages not in the archive

Subsystems (5)
lore
Share & tools
lore

Al Viro

author
#0 lore raw

PATCH 17/17 RCU'd vfsmounts

_very_ preliminary, barely tested.

fs/adfs/super.c +1 -0
index 0ff4bae..3b79d15 100644
@@ -123,6 +123,7 @@ static void adfs_put_super(struct super_block *sb)
 	for (i = 0; i < asb->s_map_size; i++)
 		brelse(asb->s_map[i].dm_bh);
 	kfree(asb->s_map);
+	synchronize_rcu();
 	kfree(asb);
 	sb->s_fs_info = NULL;
 }
fs/autofs4/inode.c +1 -0
index b104726..07599e2 100644
@@ -62,6 +62,7 @@ void autofs4_kill_sb(struct super_block *sb)
 	/* Free wait queues, close pipe */
 	autofs4_catatonic_mode(sbi);
 
+	synchronize_rcu();
 	sb->s_fs_info = NULL;
 	kfree(sbi);
 
fs/cifs/connect.c +1 -0
index a279ffc..e0305ae 100644
@@ -3779,6 +3779,7 @@ cifs_umount(struct cifs_sb_info *cifs_sb)
 
 	bdi_destroy(&cifs_sb->bdi);
 	kfree(cifs_sb->mountdata);
+	synchronize_rcu();
 	unload_nls(cifs_sb->local_nls);
 	kfree(cifs_sb);
 }
fs/dcache.c +98 -116

251 lines not on this page · raw message

fs/fat/inode.c +1 -0
index 0062da2..3d297e6 100644
@@ -557,6 +557,7 @@ static void fat_put_super(struct super_block *sb)
 	iput(sbi->fsinfo_inode);
 	iput(sbi->fat_inode);
 
+	synchronize_rcu();
 	unload_nls(sbi->nls_disk);
 	unload_nls(sbi->nls_io);
 
fs/fuse/inode.c +1 -0
index a8ce6da..2dfd2b4 100644
@@ -387,6 +387,7 @@ static void fuse_put_super(struct super_block *sb)
 	mutex_unlock(&fuse_mutex);
 	fuse_bdi_destroy(fc);
 
+	synchronize_rcu();
 	fuse_conn_put(fc);
 }
 
fs/hpfs/super.c +1 -0
index 4334cda..2946c6b 100644
@@ -109,6 +109,7 @@ static void hpfs_put_super(struct super_block *s)
 	unmark_dirty(s);
 	hpfs_unlock(s);
 
+	synchronize_rcu();
 	kfree(sbi->sb_cp_table);
 	kfree(sbi->sb_bmp_dir);
 	s->s_fs_info = NULL;
fs/mount.h +6 -4
index f086607..d64c594 100644
@@ -1,7 +1,6 @@
 #include <linux/mount.h>
 #include <linux/seq_file.h>
 #include <linux/poll.h>
-#include <linux/lglock.h>
 
 struct mnt_namespace {
 	atomic_t		count;
@@ -30,6 +29,7 @@ struct mount {
 	struct mount *mnt_parent;
 	struct dentry *mnt_mountpoint;
 	struct vfsmount mnt;
+	struct rcu_head mnt_rcu;
 #ifdef CONFIG_SMP
 	struct mnt_pcp __percpu *mnt_pcp;
 #else
@@ -80,21 +80,23 @@ static inline int is_mounted(struct vfsmount *mnt)
 extern struct mount *__lookup_mnt(struct vfsmount *, struct dentry *);
 extern struct mount *__lookup_mnt_last(struct vfsmount *, struct dentry *);
 
+extern bool legitimize_mnt(struct vfsmount *, unsigned);
+
 static inline void get_mnt_ns(struct mnt_namespace *ns)
 {
 	atomic_inc(&ns->count);
 }
 
-extern struct lglock vfsmount_lock;
+extern seqlock_t mount_lock;
 
 static inline void lock_mount_hash(void)
 {
-	br_write_lock(&vfsmount_lock);
+	write_seqlock(&mount_lock);
 }
 
 static inline void unlock_mount_hash(void)
 {
-	br_write_unlock(&vfsmount_lock);
+	write_sequnlock(&mount_lock);
 }
 
 struct proc_mounts {
fs/namei.c +37 -46

182 lines not on this page · raw message

fs/namespace.c +89 -48

277 lines not on this page · raw message

fs/ncpfs/inode.c +1 -0
index 4659da6..5539b5b 100644
@@ -792,6 +792,7 @@ static void ncp_put_super(struct super_block *sb)
 
 	ncp_stop_tasks(server);
 
+	synchronize_rcu();
 #ifdef CONFIG_NCPFS_NLS
 	/* unload the NLS charsets */
 	unload_nls(server->nls_vol);
fs/proc/root.c +1 -0
index 87dbcbe..8d1e094 100644
@@ -148,6 +148,7 @@ static void proc_kill_sb(struct super_block *sb)
 	if (ns->proc_self)
 		dput(ns->proc_self);
 	kill_anon_super(sb);
+	synchronize_rcu();	/* might be an overkill */
 	put_pid_ns(ns);
 }
 
include/linux/mount.h +2 -0
index 38cd98f..371d346 100644
@@ -49,6 +49,8 @@ struct mnt_namespace;
 
 #define MNT_LOCK_READONLY	0x400000
 #define MNT_LOCKED		0x800000
+#define MNT_DOOMED		0x1000000
+#define MNT_SYNC_UMOUNT		0x2000000
 
 struct vfsmount {
 	struct dentry *mnt_root;	/* root of the mounted tree */
include/linux/namei.h +1 -1
index 8e47bc7..492de72 100644
@@ -16,7 +16,7 @@ struct nameidata {
 	struct path	root;
 	struct inode	*inode; /* path.dentry.d_inode */
 	unsigned int	flags;
-	unsigned	seq;
+	unsigned	seq, m_seq;
 	int		last_type;
 	unsigned	depth;
 	char *saved_names[MAX_NESTED_LINKS + 1];
#5 lore raw
In reply to a message not in the archive
Quoted 3 lines · Al Viro

Anyway, I've done nicer variants of that protection for everything except fuse (hadn't gotten around to it yet); see vfs.git#experimental now:

Ok, I did a quick test, and it looks ok here, so looking good for 3.13.

However, the new smp_mb() in mntput_no_expire() is quite noticeable in the path lookup stress-test profiles. And I'm not seeing what that allegedly protects against, especially if mnt_ns is NULL (ie all the common important cases).

Linus

maintainer
#6 lore raw
Quoted 11 lines · Linus Torvalds
Quoted 3 lines · Al Viro

Anyway, I've done nicer variants of that protection for everything except fuse (hadn't gotten around to it yet); see vfs.git#experimental now:

Ok, I did a quick test, and it looks ok here, so looking good for 3.13.

However, the new smp_mb() in mntput_no_expire() is quite noticeable in the path lookup stress-test profiles. And I'm not seeing what that allegedly protects against, especially if mnt_ns is NULL (ie all the common important cases).

In the common case it's ->mnt_ns is *not* NULL; that's what we get if the damn thing is still mounted.

What we need to avoid is this:

mnt_ns non-NULL, mnt_count is 2
CPU1: umount -l CPU2: mntput
umount_tree() clears mnt_ns
drop mount_lock.lock
namespace_unlock() calls mntput()
decrement mnt_count
see that mnt_ns is NULL
grab mount_lock.lock
check mnt_count
decrement mnt_count see old value of mnt_ns decide to bugger off
see it equal to 1 (i.e. miss decrement on CPU2)
decide to bugger off

The barrier in mntput() is to prevent that combination, so that either CPU2 would see mnt_ns cleared by CPU1, or CPU1 would see mnt_count decrement done by CPU2. Its counterpart on CPU1 is provided by spin_unlock/spin_lock we've done between clearing mnt_ns and checking mnt_count. Note that synchronize_rcu() in namespace_unlock() and rcu_read_lock() in mntput() are irrelevant here - the latter on CPU2 might very well have happened after the former on CPU1, so umount -l did *not* wait for CPU2 to do anything.

Any suggestions re getting rid of that barrier?

#7 lore raw
Quoted 3 lines · Al Viro

In the common case it's ->mnt_ns is *not* NULL; that's what we get if the damn thing is still mounted.

Yeah, I misread the profile assembly code. The point being that the nice fast case now has the smp_mb() in it, and it accounts for about 60% of the cost of that function on my performance profile.

Quoted 25 lines

What we need to avoid is this:

mnt_ns non-NULL, mnt_count is 2
CPU1: umount -l CPU2: mntput
umount_tree() clears mnt_ns
drop mount_lock.lock
namespace_unlock() calls mntput()
decrement mnt_count
see that mnt_ns is NULL
grab mount_lock.lock
check mnt_count
decrement mnt_count see old value of mnt_ns decide to bugger off
see it equal to 1 (i.e. miss decrement on CPU2)
decide to bugger off

The barrier in mntput() is to prevent that combination, so that either CPU2 would see mnt_ns cleared by CPU1, or CPU1 would see mnt_count decrement done by CPU2. Its counterpart on CPU1 is provided by spin_unlock/spin_lock we've done between clearing mnt_ns and checking mnt_count. Note that synchronize_rcu() in namespace_unlock() and rcu_read_lock() in mntput() are irrelevant here - the latter on CPU2 might very well have happened after the former on CPU1, so umount -l did *not* wait for CPU2 to do anything.

Quoted 1 line

Any suggestions re getting rid of that barrier?

Hmm. The CPU2 mntput can only happen under RCU readlock, right? After the RCU grace period _and_ if the umount is going ahead, nothing should have a mnt pointer, right?

So I'm wondering if you couldn't just have a synchronize_rcu() in that umount path, after clearing mnt_ns. At that point you _know_ you're the only one that should have access to the mnt.

You'd need to drop the mount-hash lock for that. But I think you can do it in umount_tree(), right? IOW, you could make the rule be that umount_tree() must be called with the namespace lock and the mount-hash lock, and it will drop both. Or does that get too painful too?

Linus

maintainer
#8 lore raw
Quoted 3 lines · Linus Torvalds

Hmm. The CPU2 mntput can only happen under RCU readlock, right? After the RCU grace period _and_ if the umount is going ahead, nothing should have a mnt pointer, right?

umount -l doesn't care.

Quoted 3 lines

So I'm wondering if you couldn't just have a synchronize_rcu() in that umount path, after clearing mnt_ns. At that point you _know_ you're the only one that should have access to the mnt.

We have it there. See namespace_unlock(). And you are right about the locking rules for umount_tree(), except that caller is responsible for dropping those. With (potentially final) mntput() happening after both (well, as part of namespace_unlock(), done after synchronize_rcu()).

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

CPU2:
rcu_read_lock()
B = 0
read A

Are we guaranteed that we won't get both of them seeing ones, in situation when that rcu_read_lock() comes too late to be noticed by synchronize_rcu()?

#9 lore raw
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 7 lines

CPU2:
rcu_read_lock()
B = 0
read A

Are we guaranteed that we won't get both of them seeing ones, in situation when that rcu_read_lock() comes too late to be noticed by synchronize_rcu()?

Yeah, I think we should be guaranteed that, because the synchronize_rcu() will guarantee that all other CPU's go through an idle period. So the "read A" on CPU2 cannot possibly see a 1 _unless_ it happens so early that synchronize_rcu() definitely sees it (ie it's a "preexisting reader" by definition), in which case synchronize_rcu() will be waiting for a subsequent idle period, in which case the B=0 on CPU2 is not only guaranteed to happen but also be visible out, so the "read B" on CPU1 will see 0. And that's true even if CPU2 doesn't have an explicit memory barrier, because the "RCU idle" state implies that it has gone through a barrier.

So I don't see how they could possibly see ones. Modulo terminal bugs in synchronize_barrier() (which can be very slow, but for umount I wouldn't worry). Or modulo my brain being fried.

Linus

maintainer
#10 lore raw
Quoted 11 lines · Linus Torvalds

Yeah, I think we should be guaranteed that, because the synchronize_rcu() will guarantee that all other CPU's go through an idle period. So the "read A" on CPU2 cannot possibly see a 1 _unless_ it happens so early that synchronize_rcu() definitely sees it (ie it's a "preexisting reader" by definition), in which case synchronize_rcu() will be waiting for a subsequent idle period, in which case the B=0 on CPU2 is not only guaranteed to happen but also be visible out, so the "read B" on CPU1 will see 0. And that's true even if CPU2 doesn't have an explicit memory barrier, because the "RCU idle" state implies that it has gone through a barrier.

Quoted 3 lines

So I don't see how they could possibly see ones. Modulo terminal bugs in synchronize_barrier() (which can be very slow, but for umount I wouldn't worry). Or modulo my brain being fried.

There's one more place similar to that - kern_unmount(). There we also go from "longterm vfsmount, mntput() doesn't need to bother checking" to NULL ->mnt_ns. We can, of course, slap synchronize_rcu() there as well, but that might make pid_ns and ipc_ns destruction slow...

#15 lore raw
In reply to Linus Torvalds
Quoted 18 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 7 lines

CPU2:
rcu_read_lock()
B = 0
read A

Are we guaranteed that we won't get both of them seeing ones, in situation when that rcu_read_lock() comes too late to be noticed by synchronize_rcu()?

Quoted 10 lines

Yeah, I think we should be guaranteed that, because the synchronize_rcu() will guarantee that all other CPU's go through an idle period. So the "read A" on CPU2 cannot possibly see a 1 _unless_ it happens so early that synchronize_rcu() definitely sees it (ie it's a "preexisting reader" by definition), in which case synchronize_rcu() will be waiting for a subsequent idle period, in which case the B=0 on CPU2 is not only guaranteed to happen but also be visible out, so the "read B" on CPU1 will see 0. And that's true even if CPU2 doesn't have an explicit memory barrier, because the "RCU idle" state implies that it has gone through a barrier.

I think the reasoning in one direction is actually quite a bit less obvious than that.

rcu_read_unlock() does *not* necessarily imply a memory barrier (so the B=0 can actually move logically outside the rcu_read_unlock()), but synchronize_rcu() *does* imply (and enforce) that a memory barrier has occurred on all CPUs as part of quiescence. However, likewise, rcu_read_lock() doesn't imply anything in particular about writes; it does enforce either that reads can't leak earlier or that if they do a synchronize_rcu() will still wait for them, but I don't think the safety interaction between a *write* in the RCU reader and a *read* in the RCU writer necessarily follows from that enforcement.

(Also, to the best of my knowledge, you don't even need a barrier on CPU1; synchronize_rcu() should imply one.)

If synchronize_rcu() on CPU1 sees rcu_read_lock() on CPU2, then synchronize_rcu() will wait for CPU2's read-side critical section and a memory barrier before reading B, so CPU1 will see B==0.

The harder direction: If synchronize_rcu() on CPU1 does not see rcu_read_lock() on CPU2, then it won't necessarily wait for anything, and since rcu_read_lock() itself does not imply any CPU write barriers, it's not at all obvious that rcu_read_lock() prevents B=0 from occurring before CPU1's read of B.

In short, the interaction between RCU's ordering guarantees and CPU memory barriers in the presence of writes on the read side and reads on the write side does not seem sufficiently clear to support the portable use of the above pattern without an smp_wmb() on CPU2 between rcu_read_lock() and B=0. I think it might happen to work with the current implementations of RCU (with which synchronize_rcu() won't actually notice a quiescent state and return until after either the rcu_read_unlock() or a preemption point), but by the strict semantic guarantees of the RCU primitives I think you could write a legitimate RCU implementation that would break the above code.

That said, I believe this pattern *will* work with every existing implementation of RCU. Thus, I'd suggest documenting it as a warning to prospective RCU optimizers to avoid breaking the above pattern.

- Josh Triplett

#16 lore raw
Quoted 30 lines · Josh Triplett
Quoted 18 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 7 lines

CPU2:
rcu_read_lock()
B = 0
read A

Are we guaranteed that we won't get both of them seeing ones, in situation when that rcu_read_lock() comes too late to be noticed by synchronize_rcu()?

Quoted 10 lines

Yeah, I think we should be guaranteed that, because the synchronize_rcu() will guarantee that all other CPU's go through an idle period. So the "read A" on CPU2 cannot possibly see a 1 _unless_ it happens so early that synchronize_rcu() definitely sees it (ie it's a "preexisting reader" by definition), in which case synchronize_rcu() will be waiting for a subsequent idle period, in which case the B=0 on CPU2 is not only guaranteed to happen but also be visible out, so the "read B" on CPU1 will see 0. And that's true even if CPU2 doesn't have an explicit memory barrier, because the "RCU idle" state implies that it has gone through a barrier.

Quoted 4 lines

I think the reasoning in one direction is actually quite a bit less obvious than that.

rcu_read_unlock() does *not* necessarily imply a memory barrier

Don't think of it in those terms.

The only thing that matters is semantics. The semantics of synchronize_rcu() is that it needs to wait for all RCU users. It's that simple. By definition, anything inside a "rcu_read_lock()" is a RCU user, so if we have a read of memory (memory barrier or not), then synchronize_rcu() needs to wait for it. Otherwise serialize_rcu() is clearly totally broken.

Now, the fact that the normal rcu_read_lock() is just a compiler barrier may make you think "oh, it cannot work", but the thing is, the way things happens is that synchronize_rcu() ends up relying on the _scheduler_ data structures, rather than anything else. It requires seeing an idle scheduler state for each CPU after being called.

Linus

#17 lore raw
Quoted 36 lines · Linus Torvalds
Quoted 30 lines · Josh Triplett
Quoted 18 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 7 lines

CPU2:
rcu_read_lock()
B = 0
read A

Are we guaranteed that we won't get both of them seeing ones, in situation when that rcu_read_lock() comes too late to be noticed by synchronize_rcu()?

Quoted 10 lines

Yeah, I think we should be guaranteed that, because the synchronize_rcu() will guarantee that all other CPU's go through an idle period. So the "read A" on CPU2 cannot possibly see a 1 _unless_ it happens so early that synchronize_rcu() definitely sees it (ie it's a "preexisting reader" by definition), in which case synchronize_rcu() will be waiting for a subsequent idle period, in which case the B=0 on CPU2 is not only guaranteed to happen but also be visible out, so the "read B" on CPU1 will see 0. And that's true even if CPU2 doesn't have an explicit memory barrier, because the "RCU idle" state implies that it has gone through a barrier.

Quoted 4 lines

I think the reasoning in one direction is actually quite a bit less obvious than that.

rcu_read_unlock() does *not* necessarily imply a memory barrier

Quoted 8 lines

Don't think of it in those terms.

The only thing that matters is semantics. The semantics of synchronize_rcu() is that it needs to wait for all RCU users. It's that simple. By definition, anything inside a "rcu_read_lock()" is a RCU user, so if we have a read of memory (memory barrier or not), then synchronize_rcu() needs to wait for it. Otherwise serialize_rcu() is clearly totally broken.

Read, yes, but I don't think that's enough to force your example above to work in all cases. That requires semantics beyond what RCU's primitives guarantee, and I don't think you can draw conclusions about those semantics without talking about CPU memory barriers.

synchronize_rcu() says it'll wait for any in-progress reader, which includes whatever that reader might be doing. That guarantees one direction of your example above. It's a tool for controlling what the *reader* can observe. The vast majority of RCU usage models assume the writers will use a lock to guard against each other, and that readers don't make modifications. synchronize_rcu() doesn't make any particular guarantees in the other direction about what the *writer* can observe, especially in the case where synchronize_rcu() does not observe the rcu_read_lock() and doesn't need to count that reader. (Also note that B=0 is a blind write, with no read.)

The example above will work on x86 with any reasonable implementation (due to write ordering guarantees), and it should work on any architecture with all the current implementations of RCU in the Linux kernel. If we want to require that all future implementations of RCU allow the above example to work, we should document that example and associated assumption for future reference, because I don't think the semantics of the RCU primitives inherently guarantee it.

Quoted 5 lines

Now, the fact that the normal rcu_read_lock() is just a compiler barrier may make you think "oh, it cannot work", but the thing is, the way things happens is that synchronize_rcu() ends up relying on the _scheduler_ data structures, rather than anything else. It requires seeing an idle scheduler state for each CPU after being called.

That's a detail of implementation. In practice, the required semantics of synchronize_rcu() would be perfectly satisfied by an implementation that can divine that no readers are currently running without waiting for everyone to pass through the scheduler. synchronize_sched() means "everyone has scheduled"; synchronize_rcu() *only* means "any readers in-progress when I called synchronize_rcu() have finished when synchronize_rcu() returns", which does not have to imply a trip through the scheduler.

- Josh Triplett

#18 lore raw
Quoted 5 lines · Josh Triplett

Read, yes, but I don't think that's enough to force your example above to work in all cases. That requires semantics beyond what RCU's primitives guarantee, and I don't think you can draw conclusions about those semantics without talking about CPU memory barriers.

We seriosly depend on nothing leaking out. Not just reads. The "U" in RCU is "update". So it's reads, and it's writes. The fact that it says "read" in "rcu_read_lock()" doesn't mean that only reads would be affected.

And no, this still has nothing to do with memory barriers. Every single RCU user depends on the memory freeing being delayed by RCU, for example. And again, that's not just reads. It's people taking spinlocks on things that are RCU-protected etc.

So no, there is no question about this. The only question would be whether we have some RCU mode that is _buggy_, not whether you need extra memory barriers. And that is certainly possible.

Linus

maintainer
#11 lore raw
In reply to Al Viro
Quoted 8 lines · Al Viro
Quoted 3 lines

So I don't see how they could possibly see ones. Modulo terminal bugs in synchronize_barrier() (which can be very slow, but for umount I wouldn't worry). Or modulo my brain being fried.

There's one more place similar to that - kern_unmount(). There we also go from "longterm vfsmount, mntput() doesn't need to bother checking" to NULL ->mnt_ns. We can, of course, slap synchronize_rcu() there as well, but that might make pid_ns and ipc_ns destruction slow...

OK, fuse side of things done, smp_mb() in mntput_no_expire() dropped, kern_umount() got synchronize_rcu() (I'm not happy about the last one, but... hell knows; I want to see profiles before deciding what to do about it).

Updated branch force-pushed. BTW, brlock defines can go after that; we still two instances of lg_lock, but they spell the primitives out instead of using br_{read,write}_lock aliases.

Speaking of those two - I really want to see file_table.c one killed. Christoph, do you have anything along the lines of getting rid of the mark_files_ro() nonsense? After all, a combination of r/w vfsmount and a superblock with MS_RDONLY in flags should do about the right thing these days... I can probably knock something together tomorrow, but you've brought that thing up quite a few times, so if you happen to have a patch more or less ready...

#20 lore raw
In reply to Josh Triplett
Quoted 11 lines · Josh Triplett
Quoted 10 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

CPU2:
rcu_read_lock()
B = 0
read A

/me scratches his head...

OK, for CPU2 to see 1 from its read from A, the corresponding RCU read-side critical section must have started before CPU1 did A=0. This means that this same RCU read-side critical section must have started before CPU1's synchronize_rcu(), which means that it must complete before that synchronize_rcu() returns. Therefore, CPU2's B=0 must execute before CPU1's read of B, hence that read of B must return zero.

Conversely, if CPU1's read from B returns 1, we know that CPU2's RCU read-side critical section must not have completed until after CPU1's synchronize_rcu() returned, which means that the RCU read-side critical section must have started after that synchronize_rcu() started, so CPU1's assignment to A must also have already happened. Therefore, CPU2's read from A must return zero.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

Are we guaranteed that we won't get both of them seeing ones, in situation when that rcu_read_lock() comes too late to be noticed by synchronize_rcu()?

Yes, at least one of CPU1's and CPU2's reads must return zero.

For whatever it is worth, it is easier to talk about if you write it this way (easier for me, anyway):

A = 1, B = 1

CPU1:
A = 0
<full barrier>
synchronize_rcu()
r1 = B

CPU2:
rcu_read_lock()
B = 0
r2 = A

Then we are guaranteed that r1==0||r2==0.

Quoted 10 lines
Quoted 10 lines

Yeah, I think we should be guaranteed that, because the synchronize_rcu() will guarantee that all other CPU's go through an idle period. So the "read A" on CPU2 cannot possibly see a 1 _unless_ it happens so early that synchronize_rcu() definitely sees it (ie it's a "preexisting reader" by definition), in which case synchronize_rcu() will be waiting for a subsequent idle period, in which case the B=0 on CPU2 is not only guaranteed to happen but also be visible out, so the "read B" on CPU1 will see 0. And that's true even if CPU2 doesn't have an explicit memory barrier, because the "RCU idle" state implies that it has gone through a barrier.

I agree that the "<full barrier>" has no effect in this case.

The memory-barrier guarantees of RCU's grace-period primitives are documented in the excessively long header comment for synchronize_sched(), which documents an extended LKML conversation between Oleg Nesterov and myself. Here is a summary, which applies on systems with more than one CPU:

o When synchronize_sched() returns, each CPU is guaranteed to have
executed a full memory barrier since the end of its last RCU-sched read-side critical section whose beginning preceded the call to synchronize_sched().

o Each CPU having an RCU read-side critical section that extends
beyond the return from synchronize_sched() is guaranteed to have executed a full memory barrier after the beginning of synchronize_sched() and before the beginning of that RCU read-side critical section.

o If CPU A invoked synchronize_sched(), which returned to its
caller on CPU B, then both CPU A and CPU B are guaranteed to have executed a full memory barrier during the execution of synchronize_sched(). This also applies when CPUs A and B are the same CPU.

These guarantees apply to -all- CPUs, even those that are currently offline or idle. Analogous guarantees of course apply to all flavors of RCU.

Quoted 37 lines

I think the reasoning in one direction is actually quite a bit less obvious than that.

rcu_read_unlock() does *not* necessarily imply a memory barrier (so the B=0 can actually move logically outside the rcu_read_unlock()), but synchronize_rcu() *does* imply (and enforce) that a memory barrier has occurred on all CPUs as part of quiescence. However, likewise, rcu_read_lock() doesn't imply anything in particular about writes; it does enforce either that reads can't leak earlier or that if they do a synchronize_rcu() will still wait for them, but I don't think the safety interaction between a *write* in the RCU reader and a *read* in the RCU writer necessarily follows from that enforcement.

(Also, to the best of my knowledge, you don't even need a barrier on CPU1; synchronize_rcu() should imply one.)

If synchronize_rcu() on CPU1 sees rcu_read_lock() on CPU2, then synchronize_rcu() will wait for CPU2's read-side critical section and a memory barrier before reading B, so CPU1 will see B==0.

The harder direction: If synchronize_rcu() on CPU1 does not see rcu_read_lock() on CPU2, then it won't necessarily wait for anything, and since rcu_read_lock() itself does not imply any CPU write barriers, it's not at all obvious that rcu_read_lock() prevents B=0 from occurring before CPU1's read of B.

In short, the interaction between RCU's ordering guarantees and CPU memory barriers in the presence of writes on the read side and reads on the write side does not seem sufficiently clear to support the portable use of the above pattern without an smp_wmb() on CPU2 between rcu_read_lock() and B=0. I think it might happen to work with the current implementations of RCU (with which synchronize_rcu() won't actually notice a quiescent state and return until after either the rcu_read_unlock() or a preemption point), but by the strict semantic guarantees of the RCU primitives I think you could write a legitimate RCU implementation that would break the above code.

Quoted 3 lines

That said, I believe this pattern *will* work with every existing implementation of RCU. Thus, I'd suggest documenting it as a warning to prospective RCU optimizers to avoid breaking the above pattern.

I believe that the comment headers for synchronize_sched() and call_rcu() do document the required restrictions. Could you please take a look at them and let me know if I left some wiggle room that needs to be taken care of?

Thanx, Paul

#21 lore raw
Quoted 26 lines · Paul E. McKenney
Quoted 11 lines · Josh Triplett
Quoted 10 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

CPU2:
rcu_read_lock()
B = 0
read A

/me scratches his head...

OK, for CPU2 to see 1 from its read from A, the corresponding RCU read-side critical section must have started before CPU1 did A=0. This means that this same RCU read-side critical section must have started before CPU1's synchronize_rcu(), which means that it must complete before that synchronize_rcu() returns. Therefore, CPU2's B=0 must execute before CPU1's read of B, hence that read of B must return zero.

Quoted 6 lines

Conversely, if CPU1's read from B returns 1, we know that CPU2's RCU read-side critical section must not have completed until after CPU1's synchronize_rcu() returned, which means that the RCU read-side critical section must have started after that synchronize_rcu() started, so CPU1's assignment to A must also have already happened. Therefore, CPU2's read from A must return zero.

Yeah, that makes sense.

I think too much time spent staring at the *implementation* of RCU and the exciting assumptions it has to make about barriers or memory operations leaking out of the implementations of the RCU primitives (for instance, the fun needed to guarantee a memory barrier on all CPUs, or to safely use non-atomic operations inside RCU itself) makes it entirely too difficult to look at a perfectly ordinary *use* of RCU primitives and see the obvious. :)

- Josh Triplett

#22 lore raw
Quoted 36 lines · Josh Triplett
Quoted 26 lines · Paul E. McKenney
Quoted 11 lines · Josh Triplett
Quoted 10 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

CPU2:
rcu_read_lock()
B = 0
read A

/me scratches his head...

OK, for CPU2 to see 1 from its read from A, the corresponding RCU read-side critical section must have started before CPU1 did A=0. This means that this same RCU read-side critical section must have started before CPU1's synchronize_rcu(), which means that it must complete before that synchronize_rcu() returns. Therefore, CPU2's B=0 must execute before CPU1's read of B, hence that read of B must return zero.

Quoted 6 lines

Conversely, if CPU1's read from B returns 1, we know that CPU2's RCU read-side critical section must not have completed until after CPU1's synchronize_rcu() returned, which means that the RCU read-side critical section must have started after that synchronize_rcu() started, so CPU1's assignment to A must also have already happened. Therefore, CPU2's read from A must return zero.

Yeah, that makes sense.

Quoted 7 lines

I think too much time spent staring at the *implementation* of RCU and the exciting assumptions it has to make about barriers or memory operations leaking out of the implementations of the RCU primitives (for instance, the fun needed to guarantee a memory barrier on all CPUs, or to safely use non-atomic operations inside RCU itself) makes it entirely too difficult to look at a perfectly ordinary *use* of RCU primitives and see the obvious. :)

I must confess that my first thought upon seeing Al's example was "but of course CPU2's write to B and read from A can be reordered by either the compiler or the CPU!" I had to look again myself. ;-)

Thanx, Paul

#19 lore raw
In reply to Linus Torvalds
Quoted 12 lines · Linus Torvalds
Quoted 5 lines · Josh Triplett

Read, yes, but I don't think that's enough to force your example above to work in all cases. That requires semantics beyond what RCU's primitives guarantee, and I don't think you can draw conclusions about those semantics without talking about CPU memory barriers.

We seriosly depend on nothing leaking out. Not just reads. The "U" in RCU is "update". So it's reads, and it's writes. The fact that it says "read" in "rcu_read_lock()" doesn't mean that only reads would be affected.

Quoted 8 lines

And no, this still has nothing to do with memory barriers. Every single RCU user depends on the memory freeing being delayed by RCU, for example. And again, that's not just reads. It's people taking spinlocks on things that are RCU-protected etc.

So no, there is no question about this. The only question would be whether we have some RCU mode that is _buggy_, not whether you need extra memory barriers. And that is certainly possible.

Broken RCU modes are not unheard of, but Paul is extremely methodical about testing and reviewing all the details - including formal proof testing methods. There are lots of high-profile, high-frequency RCU users in the kernel that make use of every aspect of RCU semantics and any breakage would affect them as well.

There are over 2000 RCU critical sections in the kernel today, so the likelyhood of the VFS triggering an unknown bug, without other users breaking already, is fairly low. If it happens it will be fixed like other RCU bugs.

So I really wouldn't worry about it too much. If you don't mind the additional sys_umount() delay then RCU is goodness.

Thanks,

Ingo

#23 lore raw
In reply to Paul E. McKenney
Quoted 45 lines · Paul E. McKenney
Quoted 36 lines · Josh Triplett
Quoted 26 lines · Paul E. McKenney
Quoted 11 lines · Josh Triplett
Quoted 10 lines · Linus Torvalds
Quoted 9 lines · Al Viro

The problem is this:
A = 1, B = 1
CPU1:
A = 0
<full barrier>
synchronize_rcu()
read B

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

CPU2:
rcu_read_lock()
B = 0
read A

/me scratches his head...

OK, for CPU2 to see 1 from its read from A, the corresponding RCU read-side critical section must have started before CPU1 did A=0. This means that this same RCU read-side critical section must have started before CPU1's synchronize_rcu(), which means that it must complete before that synchronize_rcu() returns. Therefore, CPU2's B=0 must execute before CPU1's read of B, hence that read of B must return zero.

Quoted 6 lines

Conversely, if CPU1's read from B returns 1, we know that CPU2's RCU read-side critical section must not have completed until after CPU1's synchronize_rcu() returned, which means that the RCU read-side critical section must have started after that synchronize_rcu() started, so CPU1's assignment to A must also have already happened. Therefore, CPU2's read from A must return zero.

Yeah, that makes sense.

Quoted 7 lines

I think too much time spent staring at the *implementation* of RCU and the exciting assumptions it has to make about barriers or memory operations leaking out of the implementations of the RCU primitives (for instance, the fun needed to guarantee a memory barrier on all CPUs, or to safely use non-atomic operations inside RCU itself) makes it entirely too difficult to look at a perfectly ordinary *use* of RCU primitives and see the obvious. :)

Quoted 3 lines

I must confess that my first thought upon seeing Al's example was "but of course CPU2's write to B and read from A can be reordered by either the compiler or the CPU!" I had to look again myself. ;-)

Exactly.

- Josh Triplett

#12 lore raw
In reply to Al Viro
Quoted 7 lines · Al Viro

Speaking of those two - I really want to see file_table.c one killed. Christoph, do you have anything along the lines of getting rid of the mark_files_ro() nonsense? After all, a combination of r/w vfsmount and a superblock with MS_RDONLY in flags should do about the right thing these days... I can probably knock something together tomorrow, but you've brought that thing up quite a few times, so if you happen to have a patch more or less ready...

I used to have a patch for it that was also sent to the list long ago, but it got rid of the sysrq emergency remount r/o, which people didn't like.

maintainer
#13 lore raw
Quoted 11 lines · Christoph Hellwig
Quoted 7 lines · Al Viro

Speaking of those two - I really want to see file_table.c one killed. Christoph, do you have anything along the lines of getting rid of the mark_files_ro() nonsense? After all, a combination of r/w vfsmount and a superblock with MS_RDONLY in flags should do about the right thing these days... I can probably knock something together tomorrow, but you've brought that thing up quite a few times, so if you happen to have a patch more or less ready...

I used to have a patch for it that was also sent to the list long ago, but it got rid of the sysrq emergency remount r/o, which people didn't like.

Well... What I had in mind is less drastic; something like this (on top of #experimental); does anybody see any problems with it?

fs/file_table.c +0 -125
index e61e552..23b6dca 100644
@@ -36,8 +36,6 @@ struct files_stat_struct files_stat = {
 	.max_files = NR_FILE
 };
 
-DEFINE_STATIC_LGLOCK(files_lglock);
-
 /* SLAB cache for file structures */
 static struct kmem_cache *filp_cachep __read_mostly;
 
@@ -134,7 +132,6 @@ struct file *get_empty_filp(void)
 		return ERR_PTR(error);
 	}
 
-	INIT_LIST_HEAD(&f->f_u.fu_list);
 	atomic_long_set(&f->f_count, 1);
 	rwlock_init(&f->f_owner.lock);
 	spin_lock_init(&f->f_lock);
@@ -304,7 +301,6 @@ void fput(struct file *file)
 	if (atomic_long_dec_and_test(&file->f_count)) {
 		struct task_struct *task = current;
 
-		file_sb_list_del(file);
 		if (likely(!in_interrupt() && !(task->flags & PF_KTHREAD))) {
 			init_task_work(&file->f_u.fu_rcuhead, ____fput);
 			if (!task_work_add(task, &file->f_u.fu_rcuhead, true))
@@ -333,7 +329,6 @@ void __fput_sync(struct file *file)
 {
 	if (atomic_long_dec_and_test(&file->f_count)) {
 		struct task_struct *task = current;
-		file_sb_list_del(file);
 		BUG_ON(!(task->flags & PF_KTHREAD));
 		__fput(file);
 	}
@@ -345,129 +340,10 @@ void put_filp(struct file *file)
 {
 	if (atomic_long_dec_and_test(&file->f_count)) {
 		security_file_free(file);
-		file_sb_list_del(file);
 		file_free(file);
 	}
 }
 
-static inline int file_list_cpu(struct file *file)
-{
-#ifdef CONFIG_SMP
-	return file->f_sb_list_cpu;
-#else
-	return smp_processor_id();
-#endif
-}
-
-/* helper for file_sb_list_add to reduce ifdefs */
-static inline void __file_sb_list_add(struct file *file, struct super_block *sb)
-{
-	struct list_head *list;
-#ifdef CONFIG_SMP
-	int cpu;
-	cpu = smp_processor_id();
-	file->f_sb_list_cpu = cpu;
-	list = per_cpu_ptr(sb->s_files, cpu);
-#else
-	list = &sb->s_files;
-#endif
-	list_add(&file->f_u.fu_list, list);
-}
-
-/**
- * file_sb_list_add - add a file to the sb's file list
- * @file: file to add
- * @sb: sb to add it to
- *
- * Use this function to associate a file with the superblock of the inode it
- * refers to.
- */
-void file_sb_list_add(struct file *file, struct super_block *sb)
-{
-	if (likely(!(file->f_mode & FMODE_WRITE)))
-		return;
-	if (!S_ISREG(file_inode(file)->i_mode))
-		return;
-	lg_local_lock(&files_lglock);
-	__file_sb_list_add(file, sb);
-	lg_local_unlock(&files_lglock);
-}
-
-/**
- * file_sb_list_del - remove a file from the sb's file list
- * @file: file to remove
- * @sb: sb to remove it from
- *
- * Use this function to remove a file from its superblock.
- */
-void file_sb_list_del(struct file *file)
-{
-	if (!list_empty(&file->f_u.fu_list)) {
-		lg_local_lock_cpu(&files_lglock, file_list_cpu(file));
-		list_del_init(&file->f_u.fu_list);
-		lg_local_unlock_cpu(&files_lglock, file_list_cpu(file));
-	}
-}
-
-#ifdef CONFIG_SMP
-
-/*
- * These macros iterate all files on all CPUs for a given superblock.
- * files_lglock must be held globally.
- */
-#define do_file_list_for_each_entry(__sb, __file)		\
-{								\
-	int i;							\
-	for_each_possible_cpu(i) {				\
-		struct list_head *list;				\
-		list = per_cpu_ptr((__sb)->s_files, i);		\
-		list_for_each_entry((__file), list, f_u.fu_list)
-
-#define while_file_list_for_each_entry				\
-	}							\
-}
-
-#else
-
-#define do_file_list_for_each_entry(__sb, __file)		\
-{								\
-	struct list_head *list;					\
-	list = &(sb)->s_files;					\
-	list_for_each_entry((__file), list, f_u.fu_list)
-
-#define while_file_list_for_each_entry				\
-}
-
-#endif
-
-/**
- *	mark_files_ro - mark all files read-only
- *	@sb: superblock in question
- *
- *	All files are marked read-only.  We don't care about pending
- *	delete files so this should be used in 'force' mode only.
- */
-void mark_files_ro(struct super_block *sb)
-{
-	struct file *f;
-
-	lg_global_lock(&files_lglock);
-	do_file_list_for_each_entry(sb, f) {
-		if (!file_count(f))
-			continue;
-		if (!(f->f_mode & FMODE_WRITE))
-			continue;
-		spin_lock(&f->f_lock);
-		f->f_mode &= ~FMODE_WRITE;
-		spin_unlock(&f->f_lock);
-		if (file_check_writeable(f) != 0)
-			continue;
-		__mnt_drop_write(f->f_path.mnt);
-		file_release_write(f);
-	} while_file_list_for_each_entry;
-	lg_global_unlock(&files_lglock);
-}
-
 void __init files_init(unsigned long mempages)
 { 
 	unsigned long n;
@@ -483,6 +359,5 @@ void __init files_init(unsigned long mempages)
 	n = (mempages * (PAGE_SIZE / 1024)) / 10;
 	files_stat.max_files = max_t(unsigned long, n, NR_FILE);
 	files_defer_init();
-	lg_lock_init(&files_lglock, "files_lglock");
 	percpu_counter_init(&nr_files, 0);
 } 
fs/internal.h +0 -3
index 4a11e75..4657424 100644
@@ -73,9 +73,6 @@ extern void chroot_fs_refs(const struct path *, const struct path *);
 /*
  * file_table.c
  */
-extern void file_sb_list_add(struct file *f, struct super_block *sb);
-extern void file_sb_list_del(struct file *f);
-extern void mark_files_ro(struct super_block *);
 extern struct file *get_empty_filp(void);
 
 /*
fs/open.c +0 -2
index a1465b1..fffbed4 100644
@@ -685,7 +685,6 @@ static int do_dentry_open(struct file *f,
 	}
 
 	f->f_mapping = inode->i_mapping;
-	file_sb_list_add(f, inode->i_sb);
 
 	if (unlikely(f->f_mode & FMODE_PATH)) {
 		f->f_op = &empty_fops;
@@ -724,7 +723,6 @@ static int do_dentry_open(struct file *f,
 
 cleanup_all:
 	fops_put(f->f_op);
-	file_sb_list_del(f);
 	if (f->f_mode & FMODE_WRITE) {
 		put_write_access(inode);
 		if (!special_file(inode->i_mode)) {
fs/super.c +2 -13
index efa6e48..539d9bc 100644
@@ -140,9 +140,6 @@ static void destroy_super(struct super_block *s)
 	int i;
 	list_lru_destroy(&s->s_dentry_lru);
 	list_lru_destroy(&s->s_inode_lru);
-#ifdef CONFIG_SMP
-	free_percpu(s->s_files);
-#endif
 	for (i = 0; i < SB_FREEZE_LEVELS; i++)
 		percpu_counter_destroy(&s->s_writers.counter[i]);
 	security_sb_free(s);
@@ -172,15 +169,6 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags)
 	if (security_sb_alloc(s))
 		goto fail;
 
-#ifdef CONFIG_SMP
-	s->s_files = alloc_percpu(struct list_head);
-	if (!s->s_files)
-		goto fail;
-	for_each_possible_cpu(i)
-		INIT_LIST_HEAD(per_cpu_ptr(s->s_files, i));
-#else
-	INIT_LIST_HEAD(&s->s_files);
-#endif
 	for (i = 0; i < SB_FREEZE_LEVELS; i++) {
 		if (percpu_counter_init(&s->s_writers.counter[i], 0) < 0)
 			goto fail;
@@ -722,7 +710,8 @@ int do_remount_sb(struct super_block *sb, int flags, void *data, int force)
 	   make sure there are no rw files opened */
 	if (remount_ro) {
 		if (force) {
-			mark_files_ro(sb);
+			sb->s_readonly_remount = 1;
+			smp_wmb();
 		} else {
 			retval = sb_prepare_remount_readonly(sb);
 			if (retval)
include/linux/fs.h +0 -13
index b09e4e1..e6b0109 100644
@@ -764,12 +764,7 @@ static inline int ra_has_index(struct file_ra_state *ra, pgoff_t index)
 #define FILE_MNT_WRITE_RELEASED	2
 
 struct file {
-	/*
-	 * fu_list becomes invalid after file_free is called and queued via
-	 * fu_rcuhead for RCU freeing
-	 */
 	union {
-		struct list_head	fu_list;
 		struct llist_node	fu_llist;
 		struct rcu_head 	fu_rcuhead;
 	} f_u;
@@ -783,9 +778,6 @@ struct file {
 	 * Must not be taken from IRQ context.
 	 */
 	spinlock_t		f_lock;
-#ifdef CONFIG_SMP
-	int			f_sb_list_cpu;
-#endif
 	atomic_long_t		f_count;
 	unsigned int 		f_flags;
 	fmode_t			f_mode;
@@ -1264,11 +1256,6 @@ struct super_block {
 
 	struct list_head	s_inodes;	/* all inodes */
 	struct hlist_bl_head	s_anon;		/* anonymous dentries for (nfs) exporting */
-#ifdef CONFIG_SMP
-	struct list_head __percpu *s_files;
-#else
-	struct list_head	s_files;
-#endif
 	struct list_head	s_mounts;	/* list of mounts; _not_ for fs use */
 	struct block_device	*s_bdev;
 	struct backing_dev_info *s_bdi;
#14 lore raw

That patch looks fine to me. Having the s_readonly_remount infrastructure around certainly makes things easier.