Skip to contentSkip to conversation

fs: optimize inotify/fsnotify code for unwatched files

RFC PATCH Superseded Dave Hansen 5 participants 20 messages Jun 19, 2015 – Jun 24, 2015

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 fs: optimize inotify/fsnotify code for unwatched files

From: Dave Hansen <[email protected]>

I have a _tiny_ microbenchmark that sits in a loop and writes single bytes to a file. Writing one byte to a tmpfs file is around 2x slower than reading one byte from a file, which is a _bit_ more than I expecte. This is a dumb benchmark, but I think it's hard to deny that write() is a hot path and we should avoid unnecessary overhead there.

I did a 'perf record' of 30-second samples of read and write. The top item in a diffprofile is srcu_read_lock() from fsnotify(). There are active inotify fd's from systemd, but nothing is actually listening to the file or its part of the filesystem.

I *think* we can avoid taking the srcu_read_lock() for the common case where there are no actual marks on the file being modified *or* the vfsmount.

The *_fsnotify_mask is an aggregate of each of the masks from each mark. If we have nothing set in the masks at all then there are no marks and no need to do anything with 'ignored masks' since none exist. This keeps us from having to do the costly srcu_read_lock() for a check which is very cheap.

This patch gave a 10.8% speedup in writes/second on my test.

Cc Andrew Morton <[email protected]>
Cc Jan Kara <[email protected]>
Cc Al Viro <[email protected]>
Cc Eric Paris <[email protected]>
Cc John McCutchan <[email protected]>
Cc Robert Love <[email protected]>
Cc Tim Chen <[email protected]>
Cc Andi Kleen <[email protected]>

---

 b/fs/notify/fsnotify.c |   10 ++++++++++
 1 file changed, 10 insertions(+)
fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +10 -0
diff -puN fs/notify/fsnotify.c~optimize-fsnotify fs/notify/fsnotify.c
@@ -213,6 +213,16 @@ int fsnotify(struct inode *to_tell, __u3
 	    !(test_mask & to_tell->i_fsnotify_mask) &&
 	    !(mnt && test_mask & mnt->mnt_fsnotify_mask))
 		return 0;
+	/*
+	 * Optimization: The *_fsnotify_mask is an aggregate of each of the
+	 * masks from each mark.  If we have nothing set in the masks at
+	 * all then there are no marks and no need to do anything with
+	 * 'ignored masks' since none exist.  This keeps us from having to
+	 * do the costly srcu_read_lock() for a check which is very cheap.
+	 */
+	if (!to_tell->i_fsnotify_mask &&
+	    (!mnt || !mnt->mnt_fsnotify_mask))
+		return 0;
 
 	idx = srcu_read_lock(&fsnotify_mark_srcu);
 

_
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#1 lore raw
Quoted 16 lines · Dave Hansen

From: Dave Hansen <[email protected]>

I have a _tiny_ microbenchmark that sits in a loop and writes single bytes to a file. Writing one byte to a tmpfs file is around 2x slower than reading one byte from a file, which is a _bit_ more than I expecte. This is a dumb benchmark, but I think it's hard to deny that write() is a hot path and we should avoid unnecessary overhead there.

I did a 'perf record' of 30-second samples of read and write. The top item in a diffprofile is srcu_read_lock() from fsnotify(). There are active inotify fd's from systemd, but nothing is actually listening to the file or its part of the filesystem.

Quoted 3 lines

I *think* we can avoid taking the srcu_read_lock() for the common case where there are no actual marks on the file being modified *or* the vfsmount.

What is so expensive in it? Just the memory barrier in it?

Perhaps the function can be tuned in general.

-Andi

int __srcu_read_lock(struct srcu_struct *sp)

{
        int idx;

        idx = ACCESS_ONCE(sp->completed) & 0x1;
        preempt_disable();
        __this_cpu_inc(sp->per_cpu_ref->c[idx]);
        smp_mb(); /* B */  /* Avoid leaking the critical section. */
        __this_cpu_inc(sp->per_cpu_ref->seq[idx]);
        preempt_enable();
        return idx;
}
Quoted 45 lines

The *_fsnotify_mask is an aggregate of each of the masks from each mark. If we have nothing set in the masks at all then there are no marks and no need to do anything with 'ignored masks' since none exist. This keeps us from having to do the costly srcu_read_lock() for a check which is very cheap.

This patch gave a 10.8% speedup in writes/second on my test.

Cc Andrew Morton <[email protected]>
Cc Jan Kara <[email protected]>
Cc Al Viro <[email protected]>
Cc Eric Paris <[email protected]>
Cc John McCutchan <[email protected]>
Cc Robert Love <[email protected]>
Cc Tim Chen <[email protected]>
Cc Andi Kleen <[email protected]>

---

 b/fs/notify/fsnotify.c |   10 ++++++++++
 1 file changed, 10 insertions(+)

diff -puN fs/notify/fsnotify.c~optimize-fsnotify fs/notify/fsnotify.c

fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +10 -0
@@ -213,6 +213,16 @@ int fsnotify(struct inode *to_tell, __u3
 	    !(test_mask & to_tell->i_fsnotify_mask) &&
 	    !(mnt && test_mask & mnt->mnt_fsnotify_mask))
 		return 0;
+	/*
+	 * Optimization: The *_fsnotify_mask is an aggregate of each of the
+	 * masks from each mark.  If we have nothing set in the masks at
+	 * all then there are no marks and no need to do anything with
+	 * 'ignored masks' since none exist.  This keeps us from having to
+	 * do the costly srcu_read_lock() for a check which is very cheap.
+	 */
+	if (!to_tell->i_fsnotify_mask &&
+	    (!mnt || !mnt->mnt_fsnotify_mask))
+		return 0;
 
 	idx = srcu_read_lock(&fsnotify_mark_srcu);
 

_

Signature · 4 lines
[email protected] -- Speaking for myself only
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
Please read the FAQ at  http://www.tux.org/lkml/
#2 lore raw
Quoted 17 lines · Andi Kleen
Quoted 16 lines · Dave Hansen

From: Dave Hansen <[email protected]>

I have a _tiny_ microbenchmark that sits in a loop and writes single bytes to a file. Writing one byte to a tmpfs file is around 2x slower than reading one byte from a file, which is a _bit_ more than I expecte. This is a dumb benchmark, but I think it's hard to deny that write() is a hot path and we should avoid unnecessary overhead there.

I did a 'perf record' of 30-second samples of read and write. The top item in a diffprofile is srcu_read_lock() from fsnotify(). There are active inotify fd's from systemd, but nothing is actually listening to the file or its part of the filesystem.

Quoted 7 lines
Quoted 3 lines

I *think* we can avoid taking the srcu_read_lock() for the common case where there are no actual marks on the file being modified *or* the vfsmount.

What is so expensive in it? Just the memory barrier in it?

Perhaps the function can be tuned in general.

The memory barrier we are pretty much stuck with unless we want synchronize_srcu() to be quite a bit more expensive (and for SRCU to be unusable from offline and idle) -- and that synchronize_srcu() expense drove rewrite from the earlier version to this one. It is possible to cut down from two to one instances of __this_cpu_inc(), however.

It of course would be possible to have two types of SRCU, one for fast grace periods and the other for memory-barrier-free read-side critical sections, but obviously a very clear case would need to be made for this. At least judging from the reactions the last time I introduced a new flavor of RCU. ;-)

So, echoing Andi, what exactly is expensive?

Thanx, Paul

Quoted 58 lines

-Andi

int __srcu_read_lock(struct srcu_struct *sp)

{
        int idx;

        idx = ACCESS_ONCE(sp->completed) & 0x1;
        preempt_disable();
        __this_cpu_inc(sp->per_cpu_ref->c[idx]);
        smp_mb(); /* B */  /* Avoid leaking the critical section. */
        __this_cpu_inc(sp->per_cpu_ref->seq[idx]);
        preempt_enable();
        return idx;
}
Quoted 42 lines

The *_fsnotify_mask is an aggregate of each of the masks from each mark. If we have nothing set in the masks at all then there are no marks and no need to do anything with 'ignored masks' since none exist. This keeps us from having to do the costly srcu_read_lock() for a check which is very cheap.

This patch gave a 10.8% speedup in writes/second on my test.

Cc Andrew Morton <[email protected]>
Cc Jan Kara <[email protected]>
Cc Al Viro <[email protected]>
Cc Eric Paris <[email protected]>
Cc John McCutchan <[email protected]>
Cc Robert Love <[email protected]>
Cc Tim Chen <[email protected]>
Cc Andi Kleen <[email protected]>

---

 b/fs/notify/fsnotify.c |   10 ++++++++++
 1 file changed, 10 insertions(+)

diff -puN fs/notify/fsnotify.c~optimize-fsnotify fs/notify/fsnotify.c

fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +10 -0
@@ -213,6 +213,16 @@ int fsnotify(struct inode *to_tell, __u3
 	    !(test_mask & to_tell->i_fsnotify_mask) &&
 	    !(mnt && test_mask & mnt->mnt_fsnotify_mask))
 		return 0;
+	/*
+	 * Optimization: The *_fsnotify_mask is an aggregate of each of the
+	 * masks from each mark.  If we have nothing set in the masks at
+	 * all then there are no marks and no need to do anything with
+	 * 'ignored masks' since none exist.  This keeps us from having to
+	 * do the costly srcu_read_lock() for a check which is very cheap.
+	 */
+	if (!to_tell->i_fsnotify_mask &&
+	    (!mnt || !mnt->mnt_fsnotify_mask))
+		return 0;
 
Quoted 7 lines
Quoted 3 lines
fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +0 -0
 	idx = srcu_read_lock(&fsnotify_mark_srcu);
 

_

Signature · 1 line
[email protected] -- Speaking for myself only

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#3 lore raw
In reply to Andi Kleen
Quoted 4 lines · Andi Kleen
Quoted 3 lines
Quoted 3 lines

I *think* we can avoid taking the srcu_read_lock() for the common case where there are no actual marks on the file being modified *or* the vfsmount.

What is so expensive in it? Just the memory barrier in it?

The profiling doesn't hit on the mfence directly, but I assume that the
overhead is coming from there. The "mov 0x8(%rdi),%rcx" is identical
before and after the barrier, but it appears much more expensive _after_. That makes no sense unless the barrier is the thing causing it.

Here's how the annotation mode of 'perf top' breaks it down:

Quoted 9 lines
       │    ffffffff810fb480 <load0>:
       │      nop
       │      mov    (%rdi),%rax
  0.58 │      push   %rbp
       │      incl   %gs:0x7ef0f488(%rip)
  1.73 │      mov    %rsp,%rbp
       │      and    $0x1,%eax
       │      movslq %eax,%rdx
  0.58 │      mov    0x8(%rdi),%rcx
Quoted 9 lines
       │      incq   %gs:(%rcx,%rdx,8)
       │      mfence
 69.94 │      add    $0x2,%rdx
  7.51 │      mov    0x8(%rdi),%rcx
  4.05 │      incq   %gs:(%rcx,%rdx,8)
 13.87 │      decl   %gs:0x7ef0f45f(%rip)
       │      pop    %rbp
  1.73 │    ← retq

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#4 lore raw
Quoted 10 lines · Dave Hansen
Quoted 4 lines · Andi Kleen
Quoted 3 lines
Quoted 3 lines

I *think* we can avoid taking the srcu_read_lock() for the common case where there are no actual marks on the file being modified *or* the vfsmount.

What is so expensive in it? Just the memory barrier in it?

The profiling doesn't hit on the mfence directly, but I assume that the
overhead is coming from there. The "mov 0x8(%rdi),%rcx" is identical
before and after the barrier, but it appears much more expensive _after_. That makes no sense unless the barrier is the thing causing it.

OK, one thing to try is to simply delete the memory barrier. The resulting code will be unsafe, but will probably run well enough to get benchmark results. If it is the memory barrier, you should of course get increased throughput.

Thanx, Paul

Quoted 21 lines

Here's how the annotation mode of 'perf top' breaks it down:

Quoted 18 lines
       │    ffffffff810fb480 <load0>:
       │      nop
       │      mov    (%rdi),%rax
  0.58 │      push   %rbp
       │      incl   %gs:0x7ef0f488(%rip)
  1.73 │      mov    %rsp,%rbp
       │      and    $0x1,%eax
       │      movslq %eax,%rdx
  0.58 │      mov    0x8(%rdi),%rcx
       │      incq   %gs:(%rcx,%rdx,8)
       │      mfence
 69.94 │      add    $0x2,%rdx
  7.51 │      mov    0x8(%rdi),%rcx
  4.05 │      incq   %gs:(%rcx,%rdx,8)
 13.87 │      decl   %gs:0x7ef0f45f(%rip)
       │      pop    %rbp
  1.73 │    ← retq

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#5 lore raw
Quoted 10 lines · Paul E. McKenney
Quoted 6 lines
Quoted 6 lines
Quoted 1 line
Quoted 1 line

What is so expensive in it? Just the memory barrier in it?

The profiling doesn't hit on the mfence directly, but I assume that the
overhead is coming from there. The "mov 0x8(%rdi),%rcx" is identical
before and after the barrier, but it appears much more expensive _after_. That makes no sense unless the barrier is the thing causing it.

OK, one thing to try is to simply delete the memory barrier. The resulting code will be unsafe, but will probably run well enough to get benchmark results. If it is the memory barrier, you should of course get increased throughput.

So I took the smp_mb() out of __srcu_read_lock(). The benchmark didn't improve at all. Looking at the profile, all of the overhead had just shifted to __srcu_read_unlock() and its memory barrier! Removing the barrier in __srcu_read_unlock() got essentially the same gains out of the benchmark as the original patch in this thread that just avoids RCU.

I think that's fairly conclusive that the source of the overhead is, indeed, the memory barriers.

Although I said this test was single threaded, I also had another thought. The benchmark is single-threaded, but 'perf' is sitting doing profiling and who knows what else on the other core, and the profiling NMIs are certainly writing plenty of data to memory. So, there might be plenty of work for that smp_mb()/mfence to do _despite_ the benchmark itself being single threaded.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#6 lore raw
Quoted 21 lines · Dave Hansen
Quoted 10 lines · Paul E. McKenney
Quoted 6 lines
Quoted 6 lines
Quoted 1 line
Quoted 1 line

What is so expensive in it? Just the memory barrier in it?

The profiling doesn't hit on the mfence directly, but I assume that the
overhead is coming from there. The "mov 0x8(%rdi),%rcx" is identical
before and after the barrier, but it appears much more expensive _after_. That makes no sense unless the barrier is the thing causing it.

OK, one thing to try is to simply delete the memory barrier. The resulting code will be unsafe, but will probably run well enough to get benchmark results. If it is the memory barrier, you should of course get increased throughput.

So I took the smp_mb() out of __srcu_read_lock(). The benchmark didn't improve at all. Looking at the profile, all of the overhead had just shifted to __srcu_read_unlock() and its memory barrier! Removing the barrier in __srcu_read_unlock() got essentially the same gains out of the benchmark as the original patch in this thread that just avoids RCU.

I think that's fairly conclusive that the source of the overhead is, indeed, the memory barriers.

Quoted 6 lines

Although I said this test was single threaded, I also had another thought. The benchmark is single-threaded, but 'perf' is sitting doing profiling and who knows what else on the other core, and the profiling NMIs are certainly writing plenty of data to memory. So, there might be plenty of work for that smp_mb()/mfence to do _despite_ the benchmark itself being single threaded.

Well, it is not hard to have an SRCU-like thing that doesn't have read-side memory barriers, given that older versions of SRCU didn't have them. However, the price is increased latency for the analog to synchronize_srcu(). I am guessing that this would not be a problem for notification-group destruction, which is presumably rare.

That said, if empty *_fsnotify_mask is the common case or if the overhead of processing notification overwhelms srcu_read_lock(), your original patch seems a bit simpler.

Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#7 lore raw
Quoted 5 lines · Paul E. McKenney

Well, it is not hard to have an SRCU-like thing that doesn't have read-side memory barriers, given that older versions of SRCU didn't have them. However, the price is increased latency for the analog to synchronize_srcu(). I am guessing that this would not be a problem for notification-group destruction, which is presumably rare.

I don't think it ever makes sense to optimize for a global state. So screw sync_srcu() and make the srcu_read_lock() thing go fast.

If you need fast global state you're doing it wrong.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#8 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney

Well, it is not hard to have an SRCU-like thing that doesn't have read-side memory barriers, given that older versions of SRCU didn't have them. However, the price is increased latency for the analog to synchronize_srcu(). I am guessing that this would not be a problem for notification-group destruction, which is presumably rare.

I don't think it ever makes sense to optimize for a global state. So screw sync_srcu() and make the srcu_read_lock() thing go fast.

If you need fast global state you're doing it wrong.

That depends on how slow the resulting slow global state would be. We have some use cases (definitely KVM, perhaps also some of the VFS code) that need the current speed, as opposed to the profound slowness that three trips through synchronize_sched() would provide. Plus we would lose the ability to have SRCU readers on idle and offline CPUs.

But if Dave is willing to test it, I would be happy to send along a fast-readers patch, easy to do.

Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#9 lore raw
Quoted 4 lines · Paul E. McKenney

That depends on how slow the resulting slow global state would be. We have some use cases (definitely KVM, perhaps also some of the VFS code) that need the current speed, as opposed to the profound slowness that three trips through synchronize_sched() would provide.

But we have call_srcu() these days, not everything needs to use sync_srcu() anymore. Although I've not checked recently.

Quoted 2 lines

Plus we
would lose the ability to have SRCU readers on idle and offline CPUs.

Are we actually doing that? offline CPUs in particular seems iffy, I don't think we need (or should) worry about that. I know its been an issue with regular RCU due to tracing, but I'm not sure we should care for it for SRCU.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#10 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney

That depends on how slow the resulting slow global state would be. We have some use cases (definitely KVM, perhaps also some of the VFS code) that need the current speed, as opposed to the profound slowness that three trips through synchronize_sched() would provide.

But we have call_srcu() these days, not everything needs to use sync_srcu() anymore. Although I've not checked recently.

I believe that the KVM guys do need synchronize_srcu(), but yes, there probably are at least some cases where people might do well to move from synchronize_srcu() to call_srcu(). That said, the added complexity might or might not be worthwhile in all cases.

Quoted 7 lines
Quoted 2 lines

Plus we
would lose the ability to have SRCU readers on idle and offline CPUs.

Are we actually doing that? offline CPUs in particular seems iffy, I don't think we need (or should) worry about that. I know its been an issue with regular RCU due to tracing, but I'm not sure we should care for it for SRCU.

I believe that there still are some cases. But why would offline CPUs seem so iffy? CPUs coming up execute code before they are fully operational, and during that time, much of the kernel views them as being offline. Yet they do have to execute significant code in order to get themselves set up.

Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#11 lore raw
Quoted 5 lines · Paul E. McKenney

I believe that there still are some cases. But why would offline CPUs seem so iffy? CPUs coming up execute code before they are fully operational, and during that time, much of the kernel views them as being offline. Yet they do have to execute significant code in order to get themselves set up.

I'm thinking we do far too much during bringup and tear-down as it is. But yes maybe.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#12 lore raw
Quoted 10 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney

I believe that there still are some cases. But why would offline CPUs seem so iffy? CPUs coming up execute code before they are fully operational, and during that time, much of the kernel views them as being offline. Yet they do have to execute significant code in order to get themselves set up.

I'm thinking we do far too much during bringup and tear-down as it is. But yes maybe.

Boot, suspend, and hibernation indeed would be faster if we did less, but we still will have to do something.

Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#13 lore raw
In reply to Paul E. McKenney
Quoted 2 lines · Paul E. McKenney

But if Dave is willing to test it, I would be happy to send along a fast-readers patch, easy to do.

I'm always willing to test, but the cost of the srcu_read_lock() barrier shows up even on my 2-year-old "Intel(R) Core(TM) i5-3320M CPU @ 2.60GHz" laptop. The numbers I shared in this thread are on a newer CPU than that, so I'm fairly confident this will show up on just about any (big core) Intel CPU newer than SandyBridge.

The tests I've been running are:

https://github.com/antonblanchard/will-it-scale

with two new 1-byte read/write tests copied in to "tests/":

	https://www.sr71.net/~dave/intel/read1byte.c
	https://www.sr71.net/~dave/intel/write1byte.c

The one-byte thing is silly but it does help isolate the kernel's overhead from what the app is doing.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#14 lore raw
Quoted 14 lines · Dave Hansen
Quoted 2 lines · Paul E. McKenney

But if Dave is willing to test it, I would be happy to send along a fast-readers patch, easy to do.

I'm always willing to test, but the cost of the srcu_read_lock() barrier shows up even on my 2-year-old "Intel(R) Core(TM) i5-3320M CPU @ 2.60GHz" laptop. The numbers I shared in this thread are on a newer CPU than that, so I'm fairly confident this will show up on just about any (big core) Intel CPU newer than SandyBridge.

The tests I've been running are:

https://github.com/antonblanchard/will-it-scale

Quoted 7 lines

with two new 1-byte read/write tests copied in to "tests/":

	https://www.sr71.net/~dave/intel/read1byte.c
	https://www.sr71.net/~dave/intel/write1byte.c

The one-byte thing is silly but it does help isolate the kernel's overhead from what the app is doing.

OK, here is an experimental patch that provides a fast-readers variant of RCU, forward-ported from v3.3. Because we didn't have call_srcu() and srcu_barrier() back then, it is not a drop-in replacement for SRCU, so you need to adapt the code to the API, which means putting an "fr" in front of the "srcu" in the API members.

Understood on the overhead of the memory-barrier instruction showing up consistently. My point was instead that getting rid of this memory-barrier instruction does not come for free, as it greatly increases the latency of synchronize_frsrcu(). In a real workload, it is entirely possible that the savings from eliminating the memory barrier are overwhelmed by the increased grace-period latency.

Anyway, the patch is below. Very lightly tested.

Thanx, Paul

------------------------------------------------------------------------

commit d28d4e08ee2f87e6746ac77b07d5c94a65bcbd95

Author: Paul E. McKenney <[email protected]>
Date:   Mon Jun 22 14:51:18 2015 -0700

rcu: Add a fast-readers variant of SRCU

Dave Hansen's testing of single-byte I/O to tmpfs showed significant system-level overhead from the memory barriers in srcu_read_lock() and srcu_read_unlock().

This experimental not-for-merging commit therefore re-introduces the old variant of SRCU that avoided read-side memory barriers. This of course also introduces that variant's slow grace periods. There is no analog to call_rcu(), nor is there an analog to rcu_barrier(), so this is not a drop-in replacement for SRCU. Unlike SRCU, this implementation cannot be invoked from idle or offline CPUs. This variant therefore gets its own API: frsrcu_read_lock(), frsrcu_read_unlock(), and so on.

include/linux/frsrcu.h new file +250 -0
new file mode 100644
index 000000000000..5ad60d2d5bca
@@ -0,0 +1,250 @@
+/*
+ * Fast-Reader Sleepable Read-Copy Update mechanism for mutual exclusion
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you can access it online at
+ * http://www.gnu.org/licenses/gpl-2.0.html.
+ *
+ * Copyright (C) IBM Corporation, 2006, 2015
+ *
+ * Author: Paul McKenney <[email protected]>
+ */
+
+#ifndef _LINUX_FRSRCU_H
+#define _LINUX_FRSRCU_H
+
+#include <linux/mutex.h>
+#include <linux/rcupdate.h>
+
+struct frsrcu_struct_array {
+	int c[2];
+};
+
+struct frsrcu_struct {
+	int completed;
+	struct frsrcu_struct_array __percpu *per_cpu_ref;
+	struct mutex mutex;
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	struct lockdep_map dep_map;
+#endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
+};
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+
+int __init_frsrcu_struct(struct frsrcu_struct *frsp, const char *name,
+			 struct lock_class_key *key);
+
+#define init_frsrcu_struct(frsp) \
+({ \
+	static struct lock_class_key __frsrcu_key; \
+	\
+	__init_frsrcu_struct((frsp), #frsp, &__frsrcu_key); \
+})
+
+#define __FRSRCU_DEP_MAP_INIT(frsrcu_name) .dep_map = { .name = #frsrcu_name },
+#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
+
+int init_frsrcu_struct(struct frsrcu_struct *frsp);
+
+#define __FRSRCU_DEP_MAP_INIT(frsrcu_name)
+#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
+
+#define __FRSRCU_STRUCT_INIT(name)					\
+	{								\
+		.completed = -300,					\
+		.per_cpu_ref = &name##_frsrcu_array,			\
+		.mutex = __MUTEX_INITIALIZER(name.mutex),		\
+		__FRSRCU_DEP_MAP_INIT(name)				\
+	}
+
+/*
+ * define and init a frsrcu struct at build time.
+ * dont't call init_frsrcu_struct() nor cleanup_frsrcu_struct() on it.
+ */
+#define __DEFINE_FRSRCU(name, is_static)				\
+	static DEFINE_PER_CPU(struct frsrcu_struct_array, name##_frsrcu_array);\
+	is_static struct frsrcu_struct name = __FRSRCU_STRUCT_INIT(name)
+#define DEFINE_FRSRCU(name)		__DEFINE_FRSRCU(name, /* not static */)
+#define DEFINE_STATIC_FRSRCU(name)	__DEFINE_FRSRCU(name, static)
+
+void cleanup_frsrcu_struct(struct frsrcu_struct *frsp);
+int __frsrcu_read_lock(struct frsrcu_struct *frsp) __acquires(frsp);
+void __frsrcu_read_unlock(struct frsrcu_struct *frsp, int idx) __releases(frsp);
+void synchronize_frsrcu(struct frsrcu_struct *frsp);
+void synchronize_frsrcu_expedited(struct frsrcu_struct *frsp);
+long frsrcu_batches_completed(struct frsrcu_struct *frsp);
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+
+/**
+ * frsrcu_read_lock_held - might we be in FRSRCU read-side critical section?
+ *
+ * If CONFIG_DEBUG_LOCK_ALLOC is selected, returns nonzero iff in an FRSRCU
+ * read-side critical section.  In absence of CONFIG_DEBUG_LOCK_ALLOC,
+ * this assumes we are in an FRSRCU read-side critical section unless it can
+ * prove otherwise.
+ *
+ * Checks debug_lockdep_rcu_enabled() to prevent false positives during boot
+ * and while lockdep is disabled.
+ *
+ * Note that if the CPU is in the idle loop from an RCU point of view
+ * (ie: that we are in the section between rcu_idle_enter() and
+ * rcu_idle_exit()) then frsrcu_read_lock_held() returns false even if
+ * the CPU did an frsrcu_read_lock().  The reason for this is that RCU
+ * ignores CPUs that are in such a section, considering these as in
+ * extended quiescent state, so such a CPU is effectively never in an
+ * RCU read-side critical section regardless of what RCU primitives it
+ * invokes.  This state of affairs is required --- we need to keep an
+ * RCU-free window in idle where the CPU may possibly enter into low
+ * power mode. This way we can notice an extended quiescent state to
+ * other CPUs that started a grace period. Otherwise we would delay any
+ * grace period as long as we run in the idle task.
+ *
+ * Similarly, we avoid claiming an SRCU read lock held if the current
+ * CPU is offline.
+ */
+static inline int frsrcu_read_lock_held(struct frsrcu_struct *frsp)
+{
+	if (!debug_lockdep_rcu_enabled())
+		return 1;
+
+	if (!rcu_is_watching())
+		return 0;
+	if (!rcu_lockdep_current_cpu_online())
+		return 0;
+	return lock_is_held(&frsp->dep_map);
+}
+
+#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
+
+static inline int frsrcu_read_lock_held(struct frsrcu_struct *frsp)
+{
+	return 1;
+}
+
+#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
+
+/**
+ * frsrcu_dereference_check - fetch FRSRCU-protected pointer for later deref
+ * @p: the pointer to fetch and protect for later dereferencing
+ * @frsp: pointer to the frsrcu_struct, which is used to check that we
+ *	really are in an FRSRCU read-side critical section.
+ * @c: condition to check for update-side use
+ *
+ * If PROVE_RCU is enabled, invoking this outside of an RCU read-side
+ * critical section will result in an RCU-lockdep splat, unless @c evaluates
+ * to 1.  The @c argument will normally be a logical expression containing
+ * lockdep_is_held() calls.
+ */
+#define frsrcu_dereference_check(p, frsp, c) \
+	__rcu_dereference_check((p), frsrcu_read_lock_held(frsp) || (c), __rcu)
+
+/**
+ * frsrcu_dereference - fetch FRSRCU-protected pointer for later dereferencing
+ * @p: the pointer to fetch and protect for later dereferencing
+ * @frsp: pointer to the frsrcu_struct, which is used to check that we
+ *	really are in an FRSRCU read-side critical section.
+ *
+ * Makes rcu_dereference_check() do the dirty work.  If PROVE_RCU
+ * is enabled, invoking this outside of an RCU read-side critical
+ * section will result in an RCU-lockdep splat.
+ */
+#define frsrcu_dereference(p, frsp) frsrcu_dereference_check((p), (frsp), 0)
+
+/**
+ * frsrcu_read_lock - register a new reader for an FRSRCU-protected structure
+ * @frsp: frsrcu_struct in which to register the new reader.
+ *
+ * Enter an FRSRCU read-side critical section.  Note that FRSRCU read-side
+ * critical sections may be nested.  However, it is illegal to
+ * call anything that waits on an FRSRCU grace period for the same
+ * frsrcu_struct, whether directly or indirectly.  Please note that
+ * one way to indirectly wait on an FRSRCU grace period is to acquire
+ * a mutex that is held elsewhere while calling synchronize_srcu() or
+ * synchronize_srcu_expedited().
+ *
+ * Note that frsrcu_read_lock() and the matching frsrcu_read_unlock() must
+ * occur in the same context, for example, it is illegal to invoke
+ * frsrcu_read_unlock() in an irq handler if the matching frsrcu_read_lock()
+ * was invoked in process context.
+ */
+static inline int frsrcu_read_lock(struct frsrcu_struct *frsp) __acquires(frsp)
+{
+	int retval = __frsrcu_read_lock(frsp);
+
+	rcu_lock_acquire(&(frsp)->dep_map);
+	rcu_lockdep_assert(rcu_is_watching(),
+			   "frsrcu_read_lock() used illegally while idle");
+	return retval;
+}
+
+/**
+ * frsrcu_read_unlock - unregister old reader from FRSRCU-protected structure
+ * @frsp: frsrcu_struct in which to unregister the old reader.
+ * @idx: return value from corresponding frsrcu_read_lock().
+ *
+ * Exit an FRSRCU read-side critical section.
+ */
+static inline void frsrcu_read_unlock(struct frsrcu_struct *frsp, int idx)
+	__releases(frsp)
+{
+	rcu_lockdep_assert(rcu_is_watching(),
+			   "frsrcu_read_unlock() used illegally while idle");
+	rcu_lock_release(&(frsp)->dep_map);
+	__frsrcu_read_unlock(frsp, idx);
+}
+
+/**
+ * frsrcu_read_lock_raw - register new reader for FRSRCU-protected structure
+ * @frsp: frsrcu_struct in which to register the new reader.
+ *
+ * Enter an FRSRCU read-side critical section.  Similar to frsrcu_read_lock(),
+ * but avoids the RCU-lockdep checking.  This means that it is legal to
+ * use frsrcu_read_lock_raw() in one context, for example, in an exception
+ * handler, and then have the matching frsrcu_read_unlock_raw() in another
+ * context, for example in the task that took the exception.
+ *
+ * However, the entire FRSRCU read-side critical section must reside within
+ * a single task.  For example, beware of using frsrcu_read_lock_raw() in a
+ * device interrupt handler and frsrcu_read_unlock() in the interrupted task:
+ * This will not work if interrupts are threaded.
+ */
+static inline int frsrcu_read_lock_raw(struct frsrcu_struct *frsp)
+{
+	unsigned long flags;
+	int ret;
+
+	local_irq_save(flags);
+	ret =  __frsrcu_read_lock(frsp);
+	local_irq_restore(flags);
+	return ret;
+}
+
+/**
+ * frsrcu_read_unlock_raw - unregister reader from FRSRCU-protected structure
+ * @frsp: frsrcu_struct in which to unregister the old reader.
+ * @idx: return value from corresponding frsrcu_read_lock_raw().
+ *
+ * Exit an FRSRCU read-side critical section without lockdep-RCU checking.
+ * See frsrcu_read_lock_raw() for more details.
+ */
+static inline void frsrcu_read_unlock_raw(struct frsrcu_struct *frsp, int idx)
+{
+	unsigned long flags;
+
+	local_irq_save(flags);
+	__frsrcu_read_unlock(frsp, idx);
+	local_irq_restore(flags);
+}
+
+#endif
include/linux/rcupdate.h +1 -0
index 03a899aabd17..7ff71dbabf86 100644
@@ -69,6 +69,7 @@ void rcu_unexpedite_gp(void);
 #endif /* #else #ifdef CONFIG_TINY_RCU */
 
 enum rcutorture_type {
+	FRSRCU_FLAVOR,
 	RCU_FLAVOR,
 	RCU_BH_FLAVOR,
 	RCU_SCHED_FLAVOR,
init/Kconfig +9 -0
index 4c08197044f1..381d75cafe7d 100644
@@ -517,6 +517,15 @@ config SRCU
 	  permits arbitrary sleeping or blocking within RCU read-side critical
 	  sections.
 
+config FRSRCU
+	bool
+	help
+	  This option selects the fast-readers sleepable version of
+	  RCU. This version permits arbitrary sleeping or blocking within
+	  RCU read-side critical sections, but also avoids memory barriers
+	  within read-side markers.  Nothing comes for free, though.
+	  Grace periods are quite a bit more expensive than those of SRCU.
+
 config TASKS_RCU
 	bool
 	default n
kernel/rcu/Makefile +1 -0
index 50a808424b06..d2d7272a69bb 100644
@@ -1,4 +1,5 @@
 obj-y += update.o
+obj-$(CONFIG_FRSRCU) += frsrcu.o
 obj-$(CONFIG_SRCU) += srcu.o
 obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
 obj-$(CONFIG_TREE_RCU) += tree.o
kernel/rcu/frsrcu.c new file +320 -0

320 lines not on this page · raw message

kernel/rcu/rcutorture.c +101 -4

141 lines not on this page · raw message

lib/Kconfig.debug +1 -0
index b908048f8d6a..fb39380eb1d5 100644
@@ -1233,6 +1233,7 @@ config RCU_TORTURE_TEST
 	depends on DEBUG_KERNEL
 	select TORTURE_TEST
 	select SRCU
+	select FRSRCU
 	select TASKS_RCU
 	default n
 	help

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#15 lore raw
Quoted 6 lines · Paul E. McKenney

OK, here is an experimental patch that provides a fast-readers variant of RCU, forward-ported from v3.3. Because we didn't have call_srcu() and srcu_barrier() back then, it is not a drop-in replacement for SRCU, so you need to adapt the code to the API, which means putting an "fr" in front of the "srcu" in the API members.

Quoted 8 lines

Understood on the overhead of the memory-barrier instruction showing up consistently. My point was instead that getting rid of this memory-barrier instruction does not come for free, as it greatly increases the latency of synchronize_frsrcu(). In a real workload, it is entirely possible that the savings from eliminating the memory barrier are overwhelmed by the increased grace-period latency.

Anyway, the patch is below. Very lightly tested.

This does give a very similar performance boost as the other optimization I posted. I measured this patch to boost the writes/second by 11.0% while my previous optimization did 10.8%.

I don't think this workload will see any of the overhead of the synchronize_frsrcu(), though, but this helps confirm the source of the overhead.

#16 lore raw
Quoted 16 lines · Dave Hansen
Quoted 6 lines · Paul E. McKenney

OK, here is an experimental patch that provides a fast-readers variant of RCU, forward-ported from v3.3. Because we didn't have call_srcu() and srcu_barrier() back then, it is not a drop-in replacement for SRCU, so you need to adapt the code to the API, which means putting an "fr" in front of the "srcu" in the API members.

Quoted 8 lines

Understood on the overhead of the memory-barrier instruction showing up consistently. My point was instead that getting rid of this memory-barrier instruction does not come for free, as it greatly increases the latency of synchronize_frsrcu(). In a real workload, it is entirely possible that the savings from eliminating the memory barrier are overwhelmed by the increased grace-period latency.

Anyway, the patch is below. Very lightly tested.

Quoted 7 lines

This does give a very similar performance boost as the other optimization I posted. I measured this patch to boost the writes/second by 11.0% while my previous optimization did 10.8%.

I don't think this workload will see any of the overhead of the synchronize_frsrcu(), though, but this helps confirm the source of the overhead.

Thank you for testing it! I agree that your patch is much simpler than adding another flavor of RCU, so I prefer your patch, but the confirmation is nevertheless valuable.

Thanx, Paul

#17 lore raw
In reply to Paul E. McKenney
Quoted 4 lines · Paul E. McKenney

That depends on how slow the resulting slow global state would be. We have some use cases (definitely KVM, perhaps also some of the VFS code) that need the current speed, as opposed to the profound slowness that three trips through synchronize_sched() would provide.

So what we have with that percpu-rwsem code that I send out earlier today is a conditional smp_mb(), and I think we can do the same for SRCU.

I'm just not sure !GP is common enough for all SRCU cases to be worth doing.

Those that rely on sync_srcu() and who do it rarely would definitely benefit. The same with those that rarely do call_srcu().

But those that heavily use call_srcu() would be better off with the prolonged GP with 3 sync_sched() calls in.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

#18 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney

That depends on how slow the resulting slow global state would be. We have some use cases (definitely KVM, perhaps also some of the VFS code) that need the current speed, as opposed to the profound slowness that three trips through synchronize_sched() would provide.

Quoted 6 lines

So what we have with that percpu-rwsem code that I send out earlier today is a conditional smp_mb(), and I think we can do the same for SRCU.

I'm just not sure !GP is common enough for all SRCU cases to be worth doing.

Especially given that we don't want the readers to have to acquire a lock in order to get a consistent view of whether or not a grace period is in progress.

Quoted 5 lines

Those that rely on sync_srcu() and who do it rarely would definitely benefit. The same with those that rarely do call_srcu().

But those that heavily use call_srcu() would be better off with the prolonged GP with 3 sync_sched() calls in.

Those are indeed two likely possibilities. Other possibilities include cases where synchronize_srcu() is invoked rarely, but where its latency is visible to userspace, and those where there really is a need to wait synchronously for a grace period, so that call_srcu() doesn't buy you anything.

Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/

maintainer
#19 lore raw
In reply to Dave Hansen
Quoted 27 lines · Dave Hansen

From: Dave Hansen <[email protected]>

I have a _tiny_ microbenchmark that sits in a loop and writes single bytes to a file. Writing one byte to a tmpfs file is around 2x slower than reading one byte from a file, which is a _bit_ more than I expecte. This is a dumb benchmark, but I think it's hard to deny that write() is a hot path and we should avoid unnecessary overhead there.

I did a 'perf record' of 30-second samples of read and write. The top item in a diffprofile is srcu_read_lock() from fsnotify(). There are active inotify fd's from systemd, but nothing is actually listening to the file or its part of the filesystem.

I *think* we can avoid taking the srcu_read_lock() for the common case where there are no actual marks on the file being modified *or* the vfsmount.

The *_fsnotify_mask is an aggregate of each of the masks from each mark. If we have nothing set in the masks at all then there are no marks and no need to do anything with 'ignored masks' since none exist. This keeps us from having to do the costly srcu_read_lock() for a check which is very cheap.

This patch gave a 10.8% speedup in writes/second on my test.

...

Quoted 7 lines

diff -puN fs/notify/fsnotify.c~optimize-fsnotify fs/notify/fsnotify.c

fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +0 -0
@@ -213,6 +213,16 @@ int fsnotify(struct inode *to_tell, __u3
 	    !(test_mask & to_tell->i_fsnotify_mask) &&
 	    !(mnt && test_mask & mnt->mnt_fsnotify_mask))
 		return 0;

fs/notify/fsnotify.c int fsnotify(struct inode *to_tell, __u3 · line 225

Quoted 10 lines
fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +10 -0
+	/*
+	 * Optimization: The *_fsnotify_mask is an aggregate of each of the
+	 * masks from each mark.  If we have nothing set in the masks at
+	 * all then there are no marks and no need to do anything with
+	 * 'ignored masks' since none exist.  This keeps us from having to
+	 * do the costly srcu_read_lock() for a check which is very cheap.
+	 */
+	if (!to_tell->i_fsnotify_mask &&
+	    (!mnt || !mnt->mnt_fsnotify_mask))
+		return 0;

But this changes userspace visible behavior. You can have ignored mask set without any of the notification masks set and you are expected to clear the ignored mask on the first IN_MODIFY event. So the test just above your check is dealing with all the cases we can easily detect.

That being said we could further refine things by storing a flag in inode & struct mount telling whether any of the attached marks have ignored_mask that needs clearing set and only do the traversal of the list of marks if any of the ignored_masks is set. That will not only avoid the traversal when nobody is watching but also in cases where nobody is watching for the IN_MODIFY event.

Finally, we could do something even without the flag. We can have a look at to_tell->i_fsnotify_marks.first and mnt->mnt_fsnotify_marks.first even without SRCU to check whether they are both NULL. If they are, we know we can safely skip the SRCU thing. If they are != NULL, we grab SRCU read lock and refetch the pointers. This should be correct as we don't dereference any pointer we fetched outside of the SRCU critical section. Am I right? And this optimizes the case when nobody is watching without unwanted side-effects.

Honza

Quoted 4 lines
fs/notify/fsnotify.c renamed from fs/notify/fsnotify.c~optimize-fsnotify +0 -0
 	idx = srcu_read_lock(&fsnotify_mark_srcu);
 

_

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR