From: Darren Hart <hidden> Date: 2014-07-21 17:46:33
On 7/21/14, 10:20, "Darren Hart" [off-list ref] wrote:
On 7/21/14, 9:45, "Andi Kleen" [off-list ref] wrote:
quoted
Andi Kleen [off-list ref] writes:
quoted
Waiman Long [off-list ref] writes:
quoted
This patch series introduces two new futex command codes to support
a new optimistic spinning futex for implementing an exclusive lock
primitive that should perform better than the same primitive using
the wait-wake futex in cases where the lock owner is actively working
instead of waiting for I/O completion.
How would you distinguish those two cases automatically?
Also BTW traditionally the spinning was just done in user space.
This would be always even more efficient, because it would
even avoid the syscall entry path.
Given the glibc adaptive mutexes are not very good, but I'm sure those
could be improved.
I presented on something along these lines a few years back, and various
people have asked for the sample code over the years. Andi is right,
doing
this from user-space has the potential to be more efficient, the
challenge
is getting access to privileged information, such as the state of the
mutex owner. You don't want to spin if the owner is sleeping. I did this
by adding a tidrunning call to the vdso. My somewhat hacked solution is
still available here:
http://git.infradead.org/users/dvhart/linux.git/shortlog/refs/heads/futex/
t
idrunning/dev
I abandoned the spinning in the kernel thing due to the overhead of the
system call if I remember correctly. Also available here:
http://git.infradead.org/users/dvhart/linux.git/shortlog/refs/heads/futex/
f
utex-lock-adaptive
And the associated Linux Plumbers 2010 presentation which I can't seem to
find archived anywhere else:
http://dvhart.com/darren/files/kernel-assisted-userspace-adaptive-mutexes.p
df
We observed some significant improvements under some very specific use
cases, but a more thorough dive into performance impact in the other cases
as well as security implications with the vdso is still wanting.
--
Darren Hart Open Source Technology Center
darren.hart-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org Intel Corporation
From: Thomas Gleixner <hidden> Date: 2014-07-21 20:16:59
On Mon, 21 Jul 2014, Darren Hart wrote:
We observed some significant improvements under some very specific use
cases, but a more thorough dive into performance impact in the other cases
as well as security implications with the vdso is still wanting.
The security implication is that the feature can only be available for
process private futexes. There is no way to expose information which
crosses the process spaces.
But the way worse issue is storage.
While you can cache the namespace specific TID of a thread in the
task_struct, you still need a O(1) zero overhead mechanism to update
the thread state (only on/off cpu is interesting) in a per process
shared data structure from the guts of schedule()
For that you have basically two choices:
1) cpu_thread_id[NR_CPUS]
Simple to update from the scheduler, and a halfways moderate
storage size (NR_CPUS * 4 bytes) in the worst case, i.e. 16k
today. Set to 0 on scheduling out and to the namespace specific TID
on scheduling in.
But that requires a linear search in the user space spin loop. And
that's required for every iteration of the loop. Can you imagine
how well that works performance wise?
2) Bitmap threads_on_cpu
Again, simple to update from the scheduler, cache line bouncing
issues aside. Clear the bit on schedule out and set it on schedule
in.
But the bitmap needs the size of PID_MAX_LIMIT, which is a whopping
512k per process in the worst case.
Anything else would involve search/lookup schemes which are just
overkill in both the scheduler and the user space loop.
Now for enhanced fun you need immutable pages for that storage, as you
can't have pagefaults in the guts of schedule().
So once you found a way to make that opt-in as you don't want inflict
any of this to all processes by default, it might be a worthwhile
optimization. So the probably tolerable impact on schedule() would be
schedule_out()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
and
schedule_in()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
Anything more complex is just going to defeat the whole purpose.
Thanks,
tglx
From: Peter Zijlstra <peterz@infradead.org> Date: 2014-07-21 21:28:09
On Mon, Jul 21, 2014 at 10:16:37PM +0200, Thomas Gleixner wrote:
On Mon, 21 Jul 2014, Darren Hart wrote:
quoted
We observed some significant improvements under some very specific use
cases, but a more thorough dive into performance impact in the other cases
as well as security implications with the vdso is still wanting.
The security implication is that the feature can only be available for
process private futexes. There is no way to expose information which
crosses the process spaces.
But the way worse issue is storage.
While you can cache the namespace specific TID of a thread in the
task_struct, you still need a O(1) zero overhead mechanism to update
the thread state (only on/off cpu is interesting) in a per process
shared data structure from the guts of schedule()
For that you have basically two choices:
1) cpu_thread_id[NR_CPUS]
Simple to update from the scheduler, and a halfways moderate
storage size (NR_CPUS * 4 bytes) in the worst case, i.e. 16k
today. Set to 0 on scheduling out and to the namespace specific TID
on scheduling in.
But that requires a linear search in the user space spin loop. And
that's required for every iteration of the loop. Can you imagine
how well that works performance wise?
2) Bitmap threads_on_cpu
Again, simple to update from the scheduler, cache line bouncing
issues aside. Clear the bit on schedule out and set it on schedule
in.
But the bitmap needs the size of PID_MAX_LIMIT, which is a whopping
512k per process in the worst case.
Anything else would involve search/lookup schemes which are just
overkill in both the scheduler and the user space loop.
Now for enhanced fun you need immutable pages for that storage, as you
can't have pagefaults in the guts of schedule().
So once you found a way to make that opt-in as you don't want inflict
any of this to all processes by default, it might be a worthwhile
optimization. So the probably tolerable impact on schedule() would be
schedule_out()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
and
schedule_in()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
Anything more complex is just going to defeat the whole purpose.
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
From: Andy Lutomirski <luto@amacapital.net> Date: 2014-07-21 21:31:58
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref] wrote:
On Mon, Jul 21, 2014 at 10:16:37PM +0200, Thomas Gleixner wrote:
quoted
On Mon, 21 Jul 2014, Darren Hart wrote:
quoted
We observed some significant improvements under some very specific use
cases, but a more thorough dive into performance impact in the other cases
as well as security implications with the vdso is still wanting.
The security implication is that the feature can only be available for
process private futexes. There is no way to expose information which
crosses the process spaces.
But the way worse issue is storage.
While you can cache the namespace specific TID of a thread in the
task_struct, you still need a O(1) zero overhead mechanism to update
the thread state (only on/off cpu is interesting) in a per process
shared data structure from the guts of schedule()
For that you have basically two choices:
1) cpu_thread_id[NR_CPUS]
Simple to update from the scheduler, and a halfways moderate
storage size (NR_CPUS * 4 bytes) in the worst case, i.e. 16k
today. Set to 0 on scheduling out and to the namespace specific TID
on scheduling in.
But that requires a linear search in the user space spin loop. And
that's required for every iteration of the loop. Can you imagine
how well that works performance wise?
2) Bitmap threads_on_cpu
Again, simple to update from the scheduler, cache line bouncing
issues aside. Clear the bit on schedule out and set it on schedule
in.
But the bitmap needs the size of PID_MAX_LIMIT, which is a whopping
512k per process in the worst case.
Anything else would involve search/lookup schemes which are just
overkill in both the scheduler and the user space loop.
Now for enhanced fun you need immutable pages for that storage, as you
can't have pagefaults in the guts of schedule().
So once you found a way to make that opt-in as you don't want inflict
any of this to all processes by default, it might be a worthwhile
optimization. So the probably tolerable impact on schedule() would be
schedule_out()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
and
schedule_in()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
Anything more complex is just going to defeat the whole purpose.
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
--Andy
--
To unsubscribe from this list: send the line "unsubscribe linux-api" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
From: Thomas Gleixner <hidden> Date: 2014-07-21 21:44:14
On Mon, 21 Jul 2014, Peter Zijlstra wrote:
On Mon, Jul 21, 2014 at 10:16:37PM +0200, Thomas Gleixner wrote:
quoted
On Mon, 21 Jul 2014, Darren Hart wrote:
quoted
We observed some significant improvements under some very specific use
cases, but a more thorough dive into performance impact in the other cases
as well as security implications with the vdso is still wanting.
The security implication is that the feature can only be available for
process private futexes. There is no way to expose information which
crosses the process spaces.
But the way worse issue is storage.
While you can cache the namespace specific TID of a thread in the
task_struct, you still need a O(1) zero overhead mechanism to update
the thread state (only on/off cpu is interesting) in a per process
shared data structure from the guts of schedule()
For that you have basically two choices:
1) cpu_thread_id[NR_CPUS]
Simple to update from the scheduler, and a halfways moderate
storage size (NR_CPUS * 4 bytes) in the worst case, i.e. 16k
today. Set to 0 on scheduling out and to the namespace specific TID
on scheduling in.
But that requires a linear search in the user space spin loop. And
that's required for every iteration of the loop. Can you imagine
how well that works performance wise?
2) Bitmap threads_on_cpu
Again, simple to update from the scheduler, cache line bouncing
issues aside. Clear the bit on schedule out and set it on schedule
in.
But the bitmap needs the size of PID_MAX_LIMIT, which is a whopping
512k per process in the worst case.
Anything else would involve search/lookup schemes which are just
overkill in both the scheduler and the user space loop.
Now for enhanced fun you need immutable pages for that storage, as you
can't have pagefaults in the guts of schedule().
So once you found a way to make that opt-in as you don't want inflict
any of this to all processes by default, it might be a worthwhile
optimization. So the probably tolerable impact on schedule() would be
schedule_out()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
and
schedule_in()
if (curr->threads_on_cpu)
clear_bit(curr->ns_tid, curr->threads_on_cpu);
Anything more complex is just going to defeat the whole purpose.
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
I completely agree.
This wants to backed by proper numbers taken from a proper
implementation and not from some randomly cobbled together works for
me hackery.
As I said: It might be a worthwhile optimization....
Thanks,
tglx
From: Thomas Gleixner <hidden> Date: 2014-07-21 21:47:23
On Mon, 21 Jul 2014, Andy Lutomirski wrote:
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref] wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
So it's a non issue indeed and definitely not worth the trouble of
that extra storage, the scheduler overhead, etc.
Summary: Once you can't take it atomically in user space, you've lost
anyway. And we are better off to do the magic spinning in
kernel where we have all the information accessible already.
Thanks,
tglx
From: Darren Hart <hidden> Date: 2014-07-21 22:41:57
On 7/21/14, 14:47, "Thomas Gleixner" [off-list ref] wrote:
On Mon, 21 Jul 2014, Andy Lutomirski wrote:
quoted
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref]
wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
So it's a non issue indeed and definitely not worth the trouble of
that extra storage, the scheduler overhead, etc.
Summary: Once you can't take it atomically in user space, you've lost
anyway. And we are better off to do the magic spinning in
kernel where we have all the information accessible already.
And we have such an implementation with the FUTEX_LOCK_ADAPTIVE code we
discussed back in Oct 2010 (purely kernel, no VDSO), updated with some of
your and other's comments:
http://git.infradead.org/users/dvhart/linux.git/shortlog/refs/heads/futex/f
utex-lock/v7
I can work on forward porting this series to current mainline (post recent
security fixes) and cleaning up the commentary and such if people are
interested in seeing this implementation (based on Peter Z's spinning
mutex work iirc) resurrected...
--
Darren Hart Open Source Technology Center
darren.hart@intel.com Intel Corporation
On Mon, 2014-07-21 at 14:31 -0700, Andy Lutomirski wrote:
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref] wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
From: Thomas Gleixner <hidden> Date: 2014-07-22 01:01:30
On Mon, 21 Jul 2014, Darren Hart wrote:
On 7/21/14, 14:47, "Thomas Gleixner" [off-list ref] wrote:
quoted
On Mon, 21 Jul 2014, Andy Lutomirski wrote:
quoted
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref]
wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
So it's a non issue indeed and definitely not worth the trouble of
that extra storage, the scheduler overhead, etc.
Summary: Once you can't take it atomically in user space, you've lost
anyway. And we are better off to do the magic spinning in
kernel where we have all the information accessible already.
And we have such an implementation with the FUTEX_LOCK_ADAPTIVE code we
discussed back in Oct 2010 (purely kernel, no VDSO), updated with some of
your and other's comments:
http://git.infradead.org/users/dvhart/linux.git/shortlog/refs/heads/futex/f
utex-lock/v7
I can work on forward porting this series to current mainline (post recent
security fixes) and cleaning up the commentary and such if people are
interested in seeing this implementation (based on Peter Z's spinning
mutex work iirc) resurrected...
No. We really want to avoid more magic hackery in the futex code.
Lets sit down and think about what we need:
1) Support for all existing features
2) More fine grained locking
3) Optimistic spinning
@1: No discussion about that. Period.
We are not going to introduce some new futex opcode, which is
optimized for a microbenchmark and ignoring all of the pain we
went through in the last 10 years. No way, especially after the
recent security disaster.
@2 and @3: Yes, we want that.
But again, we don't add fine grained locking just for some half
baken new opcode. No, we are adding it where it makes the most
sense and lets us reuse most of the code.
I can predict your question, how that should work :)
If we want to have fine grained locking beyond the futex hash
buckets and that's something we discussed before, you need a state
representation of the user space futex in the kernel. That's what
Waiman added as well, just in a way that's beyond repair.
The charm of the futex hash buckets is that they do not create
kernel state because the futex_q which is enqueued into the bucket
is on the task stack of the task which is blocked on the futex.
So much for the theory, because that stopped to be true when we
added support for PI futexes. They already create kernel internal
state which is not magically removed when the thread exits the
syscall. It's called pi_state.
Now the question is how is this related to the non PI magic
spinning optimization? Very much so.
Simply because the handling of pi_state already covers ALL the
corner cases which come with the extra kernel internal state and
they provide the full function set of futexes required by the
various (ab)use cases including the requeue functionality which is
required for condvars. It even supports caching of the pi_state
struct in a way which makes sense, rather than blindly slapping a
cached entry onto each hash bucket.
So it's not a really mind boggling thought experiment to think
about this magic new feature as a subset of the already existing
PI futex code. It is a subset, just minus the PI portion plus the
more fine grained locking.
So the right solution is to rework the existing code.
1) Make pi_state the entity which gets enqueued into the hash bucket
and manage the waiters in a pi_state internal queue.
Straight forward problem as it is still protected by the hash
bucket lock.
2) Add private locking to the pi_state to reduce the lock contention
on the hash bucket lock.
Straight forward conversion as well
3) Make mutex a subset of rt_mutex
That makes a lot of sense, simply because a mutex is the same as a
rtmutex just without the PI part.
Just for the record before anyone cries murder: The original mutex
implemention was modeled after the rtmutex one in the first place
and the optimistic spinning was first introduced on rtmutexes by
Gregory Haskins et. al. in the context of the RT tree. Back then it
was too early or we were simply too stupid to see the similarities
and opted for a complete separate implementation.
Yes, I'm aware that this is a non-trivial problem, but if you look
at the details, then the non-trivial part is in the slow path were
stuff actually goes to sleep. The fast path of mutex and rt_mutex
is simply the same. So there is no reason to keep them separate. An
extra conditional in the slow path is not going to hurt at all.
Surely, you might say, that I'm an egoistic bastard, who just wants
to have the benefit of MCS for rtmutex for free. Right you are, but
there is a whole bunch of reasons why this makes tons of sense:
- As I said above, it's almost the same, except for the slow path
details, where a few extra conditionals do not matter
- Sharing the code has the obvious benefits. And it's not only
sharing between rtmutex and mutex, it's also sharing the
underlying optimizations of MCS for the kernel internal users and
the user space exposed ones, i.e. futexes.
- Once unified the desired futex functionality just works with a
minimal impact on the futex code itself.
The futex code does not care whether the underlying primitive has
PI semantics or not, it just cares that all the required features
like proxy locking etc. are in place. And that everything like
timeouts, requeue etc. is just supported.
- The semantics of the new futex functionality has not to be
defined again. We can simply reuse the rather well defined and
well tested straight forward semantics of the existing PI
opcodes.
- That minimizes the risk massively, because all state and error
handling is common code.
- Any update to the underlying primitives will benefit ALL usage
sites and reduces the copy and paste induced hell of MCS code
sprinkled all over the kernel.
4) Enable user space to make use of it.
Whether this will be a separate opcode or just a new flag to the
existing PI opcodes is going to be just a bikeshedding question at
that point. :)
The important point is, that we do NOT grow any new unmaintainable
warts to the futex code. And the 650+ new lines of hackery which come
with the proposed patch set are in no way acceptable, especially as
they only cover the minimalistic functionality set of futexes. Not to
talk about the other issues I've observed on the first glance.
So before anyone comes up with a "solution" for all of this tomorrow
afternoon in form of another half baken patch, please sit back mull it
in your head and lets have a proper discussion about the approach
first.
Thanks,
tglx
From: Steven Rostedt <rostedt@goodmis.org> Date: 2014-07-22 01:35:02
On Tue, 22 Jul 2014 03:01:00 +0200 (CEST)
Thomas Gleixner [off-list ref] wrote:
On Mon, 21 Jul 2014, Darren Hart wrote:
quoted
On 7/21/14, 14:47, "Thomas Gleixner" [off-list ref] wrote:
quoted
On Mon, 21 Jul 2014, Andy Lutomirski wrote:
quoted
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref]
wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
So it's a non issue indeed and definitely not worth the trouble of
that extra storage, the scheduler overhead, etc.
Summary: Once you can't take it atomically in user space, you've lost
anyway. And we are better off to do the magic spinning in
kernel where we have all the information accessible already.
I just want to point out that I was having a very nice conversation
with Robert Haas (Cc'd) in Napa Valley at Linux Collaboration about
this very topic. Robert is a PostgeSQL developer who told me that they
implement their spin locks completely in userspace (no futex, just raw
spinning on shared memory). This is because the sleep on contention of a
futex has shown to be very expensive in their benchmarks. His work is
not a micro benchmark but for a very popular database where locking is
crucial.
I was telling Robert that if futexes get optimistic spinning, he should
reconsider their use of userspace spinlocks in favor of this, because
I'm pretty sure that they will see a great improvement.
Now Robert will be the best one to answer if the system call is indeed
more expensive than doing full spins in userspace. If the spin is done
in the kernel and they still get better performance by just spinning
blindly in userspace even if the owner is asleep, I think we will have
our answer.
Note, I believe they only care about shared threads, and this
optimistic spinning does not need to be something done between
processes.
quoted
And we have such an implementation with the FUTEX_LOCK_ADAPTIVE code we
discussed back in Oct 2010 (purely kernel, no VDSO), updated with some of
your and other's comments:
http://git.infradead.org/users/dvhart/linux.git/shortlog/refs/heads/futex/f
utex-lock/v7
I can work on forward porting this series to current mainline (post recent
security fixes) and cleaning up the commentary and such if people are
interested in seeing this implementation (based on Peter Z's spinning
mutex work iirc) resurrected...
No. We really want to avoid more magic hackery in the futex code.
Lets sit down and think about what we need:
1) Support for all existing features
2) More fine grained locking
3) Optimistic spinning
@1: No discussion about that. Period.
We are not going to introduce some new futex opcode, which is
optimized for a microbenchmark and ignoring all of the pain we
went through in the last 10 years. No way, especially after the
recent security disaster.
@2 and @3: Yes, we want that.
But again, we don't add fine grained locking just for some half
baken new opcode. No, we are adding it where it makes the most
sense and lets us reuse most of the code.
I can predict your question, how that should work :)
If we want to have fine grained locking beyond the futex hash
buckets and that's something we discussed before, you need a state
representation of the user space futex in the kernel. That's what
Waiman added as well, just in a way that's beyond repair.
The charm of the futex hash buckets is that they do not create
kernel state because the futex_q which is enqueued into the bucket
is on the task stack of the task which is blocked on the futex.
So much for the theory, because that stopped to be true when we
added support for PI futexes. They already create kernel internal
state which is not magically removed when the thread exits the
syscall. It's called pi_state.
Now the question is how is this related to the non PI magic
spinning optimization? Very much so.
Simply because the handling of pi_state already covers ALL the
corner cases which come with the extra kernel internal state and
they provide the full function set of futexes required by the
various (ab)use cases including the requeue functionality which is
required for condvars. It even supports caching of the pi_state
struct in a way which makes sense, rather than blindly slapping a
cached entry onto each hash bucket.
So it's not a really mind boggling thought experiment to think
about this magic new feature as a subset of the already existing
PI futex code. It is a subset, just minus the PI portion plus the
more fine grained locking.
So the right solution is to rework the existing code.
1) Make pi_state the entity which gets enqueued into the hash bucket
and manage the waiters in a pi_state internal queue.
Straight forward problem as it is still protected by the hash
bucket lock.
2) Add private locking to the pi_state to reduce the lock contention
on the hash bucket lock.
Straight forward conversion as well
3) Make mutex a subset of rt_mutex
+1
That makes a lot of sense, simply because a mutex is the same as a
rtmutex just without the PI part.
Just for the record before anyone cries murder: The original mutex
implemention was modeled after the rtmutex one in the first place
and the optimistic spinning was first introduced on rtmutexes by
Gregory Haskins et. al. in the context of the RT tree. Back then it
was too early or we were simply too stupid to see the similarities
and opted for a complete separate implementation.
I believe it was more about politics to why it was a separate solution.
Technically, I think they should have been one.
Yes, I'm aware that this is a non-trivial problem, but if you look
at the details, then the non-trivial part is in the slow path were
stuff actually goes to sleep. The fast path of mutex and rt_mutex
is simply the same. So there is no reason to keep them separate. An
extra conditional in the slow path is not going to hurt at all.
Surely, you might say, that I'm an egoistic bastard, who just wants
to have the benefit of MCS for rtmutex for free. Right you are, but
there is a whole bunch of reasons why this makes tons of sense:
- As I said above, it's almost the same, except for the slow path
details, where a few extra conditionals do not matter
- Sharing the code has the obvious benefits. And it's not only
sharing between rtmutex and mutex, it's also sharing the
underlying optimizations of MCS for the kernel internal users and
the user space exposed ones, i.e. futexes.
- Once unified the desired futex functionality just works with a
minimal impact on the futex code itself.
The futex code does not care whether the underlying primitive has
PI semantics or not, it just cares that all the required features
like proxy locking etc. are in place. And that everything like
timeouts, requeue etc. is just supported.
- The semantics of the new futex functionality has not to be
defined again. We can simply reuse the rather well defined and
well tested straight forward semantics of the existing PI
opcodes.
- That minimizes the risk massively, because all state and error
handling is common code.
- Any update to the underlying primitives will benefit ALL usage
sites and reduces the copy and paste induced hell of MCS code
sprinkled all over the kernel.
4) Enable user space to make use of it.
Whether this will be a separate opcode or just a new flag to the
existing PI opcodes is going to be just a bikeshedding question at
that point. :)
The important point is, that we do NOT grow any new unmaintainable
warts to the futex code. And the 650+ new lines of hackery which come
with the proposed patch set are in no way acceptable, especially as
they only cover the minimalistic functionality set of futexes. Not to
talk about the other issues I've observed on the first glance.
So before anyone comes up with a "solution" for all of this tomorrow
afternoon in form of another half baken patch, please sit back mull it
in your head and lets have a proper discussion about the approach
first.
If we can have that schedule_out() threads_on_cpu, that could be a
helpful solution to see if the system call is indeed expensive. Sounds
like we can have both an in kernel solution and a userspace one as well.
-- Steve
From: Mike Galbraith <hidden> Date: 2014-07-22 02:31:20
On Mon, 2014-07-21 at 21:34 -0400, Steven Rostedt wrote:
I was telling Robert that if futexes get optimistic spinning, he should
reconsider their use of userspace spinlocks in favor of this, because
I'm pretty sure that they will see a great improvement.
My (dated) experience with pgsql says you're likely right.
Once upon a time, preempting a userspace spinlock owner caused pgsql to
collapse into a quivering heap. The scheduler trying to hand the CPU
back to a preempted task instead of selecting what was strictly speaking
the most deserving task afterward (LAST_BUDDY) let pgsql+oltp scale nice
and flat instead of self destructing, but the root cause of collapse was
spinners lacking knowledge. With spin done in kernel, you can know
when spinning is a waste of perfectly good cycles.
-Mike
On Mon, 2014-07-21 at 21:34 -0400, Steven Rostedt wrote:
On Tue, 22 Jul 2014 03:01:00 +0200 (CEST)
Thomas Gleixner [off-list ref] wrote:
quoted
On Mon, 21 Jul 2014, Darren Hart wrote:
quoted
On 7/21/14, 14:47, "Thomas Gleixner" [off-list ref] wrote:
quoted
On Mon, 21 Jul 2014, Andy Lutomirski wrote:
quoted
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref]
wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
So it's a non issue indeed and definitely not worth the trouble of
that extra storage, the scheduler overhead, etc.
Summary: Once you can't take it atomically in user space, you've lost
anyway. And we are better off to do the magic spinning in
kernel where we have all the information accessible already.
I just want to point out that I was having a very nice conversation
with Robert Haas (Cc'd) in Napa Valley at Linux Collaboration about
this very topic. Robert is a PostgeSQL developer who told me that they
implement their spin locks completely in userspace (no futex, just raw
spinning on shared memory). This is because the sleep on contention of a
futex has shown to be very expensive in their benchmarks.
Well sure, hashing, plist handling, wakeups etc. (not to mention
dirtying cachelines). The "fast" in futex is only due to the fact that
there is no jump to kernel space when the lock is uncontended after say,
a successful cmpxchg in user space. Once futex(2) is actually called,
performance is quite a different story.
His work is
not a micro benchmark but for a very popular database where locking is
crucial.
I was telling Robert that if futexes get optimistic spinning, he should
reconsider their use of userspace spinlocks in favor of this, because
I'm pretty sure that they will see a great improvement.
Agreed, with the critical regions being correctly sized for spinning
locks.
Now Robert will be the best one to answer if the system call is indeed
more expensive than doing full spins in userspace. If the spin is done
in the kernel and they still get better performance by just spinning
blindly in userspace even if the owner is asleep, I think we will have
our answer.
Note, I believe they only care about shared threads, and this
optimistic spinning does not need to be something done between
processes.
With the pi_state there would be no such distinction.
Thanks,
Davidlohr
From: Peter Zijlstra <peterz@infradead.org> Date: 2014-07-22 07:35:46
On Mon, Jul 21, 2014 at 05:32:55PM -0700, Davidlohr Bueso wrote:
On Mon, 2014-07-21 at 14:31 -0700, Andy Lutomirski wrote:
quoted
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra [off-list ref] wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
@@ -323,6 +323,7 @@ 314 common sched_setattr sys_sched_setattr 315 common sched_getattr sys_sched_getattr 316 common renameat2 sys_renameat2+317 common nop sys_nop # # x32-specific system call numbers start at 512 to avoid cache impact
From: Peter Zijlstra <peterz@infradead.org> Date: 2014-07-22 07:47:27
On Mon, Jul 21, 2014 at 09:34:57PM -0400, Steven Rostedt wrote:
I just want to point out that I was having a very nice conversation
with Robert Haas (Cc'd) in Napa Valley at Linux Collaboration about
this very topic. Robert is a PostgeSQL developer who told me that they
implement their spin locks completely in userspace (no futex, just raw
spinning on shared memory). This is because the sleep on contention of a
futex has shown to be very expensive in their benchmarks. His work is
not a micro benchmark but for a very popular database where locking is
crucial.
Userspace spinlocks are a clusterfuck. Its impossible to solve the
priority inversion trainwrecks they cause _ever_.
We've had -- as I think Mike already pointed out -- tons of 'fun' with
psql exactly because its doing this :-(
I was telling Robert that if futexes get optimistic spinning, he should
reconsider their use of userspace spinlocks in favor of this, because
I'm pretty sure that they will see a great improvement.
Now Robert will be the best one to answer if the system call is indeed
more expensive than doing full spins in userspace. If the spin is done
in the kernel and they still get better performance by just spinning
blindly in userspace even if the owner is asleep, I think we will have
our answer.
No, the best way is to measure the exact syscall cost. If he still gets
better performance we need to analyze why, there might be something else
hiding there.
Note, I believe they only care about shared threads, and this
optimistic spinning does not need to be something done between
processes.
There's no reason not to provide it for shared futexes, in fact I
suspect not doing it for shared futexes is going to make the code
uglier.
Anyway, there is one big fail in the entire futex stack that we 'need'
to sort some day and that is NUMA. Some people (again database people)
explicitly do not use futexes and instead use sysvsem because of this.
The problem with numa futexes is that because they're vaddr based there
is no (persistent) node information. You always end up having to fall
back to looking in all nodes before you can guarantee there is no
matching futex.
One way to achieve it is by extending the futex value to include a node
number, but that's obviously a complete ABI break. Then again, it should
be pretty straight fwd, since the node number doesn't need to be part of
the actual atomic update part, just part of the userspace storage.
From: Thomas Gleixner <hidden> Date: 2014-07-22 08:40:05
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
Anyway, there is one big fail in the entire futex stack that we 'need'
to sort some day and that is NUMA. Some people (again database people)
explicitly do not use futexes and instead use sysvsem because of this.
The problem with numa futexes is that because they're vaddr based there
is no (persistent) node information. You always end up having to fall
back to looking in all nodes before you can guarantee there is no
matching futex.
One way to achieve it is by extending the futex value to include a node
number, but that's obviously a complete ABI break. Then again, it should
be pretty straight fwd, since the node number doesn't need to be part of
the actual atomic update part, just part of the userspace storage.
So you want per node hash buckets, right? Fair enough, but how do you
make sure, that no thread/process on a different node is fiddling with
that "node bound" futex as well?
Thanks,
tglx
From: Peter Zijlstra <peterz@infradead.org> Date: 2014-07-22 08:48:52
On Tue, Jul 22, 2014 at 10:39:17AM +0200, Thomas Gleixner wrote:
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
quoted
Anyway, there is one big fail in the entire futex stack that we 'need'
to sort some day and that is NUMA. Some people (again database people)
explicitly do not use futexes and instead use sysvsem because of this.
The problem with numa futexes is that because they're vaddr based there
is no (persistent) node information. You always end up having to fall
back to looking in all nodes before you can guarantee there is no
matching futex.
One way to achieve it is by extending the futex value to include a node
number, but that's obviously a complete ABI break. Then again, it should
be pretty straight fwd, since the node number doesn't need to be part of
the actual atomic update part, just part of the userspace storage.
So you want per node hash buckets, right? Fair enough, but how do you
make sure, that no thread/process on a different node is fiddling with
that "node bound" futex as well?
You don't and that should work just as well, just slower. But since the
node id is in the futex 'value' we'll always end up in the right
node-hash, even if its a remote one.
So yes, per node hashes, and a persistent futex->node map.
And before people start talking about mempol and using that to bind
memory to nodes and such, remember that private futexes do not have a
vma lookup and therefore mempols are impossible to use.
From: Thomas Gleixner <hidden> Date: 2014-07-22 10:00:25
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
On Tue, Jul 22, 2014 at 10:39:17AM +0200, Thomas Gleixner wrote:
quoted
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
quoted
Anyway, there is one big fail in the entire futex stack that we 'need'
to sort some day and that is NUMA. Some people (again database people)
explicitly do not use futexes and instead use sysvsem because of this.
The problem with numa futexes is that because they're vaddr based there
is no (persistent) node information. You always end up having to fall
back to looking in all nodes before you can guarantee there is no
matching futex.
One way to achieve it is by extending the futex value to include a node
number, but that's obviously a complete ABI break. Then again, it should
be pretty straight fwd, since the node number doesn't need to be part of
the actual atomic update part, just part of the userspace storage.
So you want per node hash buckets, right? Fair enough, but how do you
make sure, that no thread/process on a different node is fiddling with
that "node bound" futex as well?
You don't and that should work just as well, just slower. But since the
node id is in the futex 'value' we'll always end up in the right
node-hash, even if its a remote one.
So yes, per node hashes, and a persistent futex->node map.
Which works fine as long as you only have the futex_q on the stack of
the blocked task. If user space is lying to you, then you just end up
with a bunch of threads sleeping forever. Who cares?
But if you create independent kernel state, which we have with
pi_state and which you need for finegrained locking and further
spinning fun, you open up another can of worms. Simply because this
would enable rogue user space to create multiple instances of the
kernel internal state. I can predict the CVEs resulting from that
even without using a crystal ball.
Thanks,
tglx
From: Waiman Long <hidden> Date: 2014-07-22 20:21:16
On 07/21/2014 09:01 PM, Thomas Gleixner wrote:
On Mon, 21 Jul 2014, Darren Hart wrote:
quoted
On 7/21/14, 14:47, "Thomas Gleixner"[off-list ref] wrote:
quoted
On Mon, 21 Jul 2014, Andy Lutomirski wrote:
quoted
On Mon, Jul 21, 2014 at 2:27 PM, Peter Zijlstra[off-list ref]
wrote:
quoted
All this is predicated on the fact that syscalls are 'expensive'.
Weren't syscalls only 100s of cycles? All this bitmap mucking is far
more expensive due to cacheline misses, which due to the size of the
things is almost guaranteed.
120 - 300 cycles for me, unless tracing happens, and I'm working on
reducing the incidence of tracing.
So it's a non issue indeed and definitely not worth the trouble of
that extra storage, the scheduler overhead, etc.
Summary: Once you can't take it atomically in user space, you've lost
anyway. And we are better off to do the magic spinning in
kernel where we have all the information accessible already.
And we have such an implementation with the FUTEX_LOCK_ADAPTIVE code we
discussed back in Oct 2010 (purely kernel, no VDSO), updated with some of
your and other's comments:
http://git.infradead.org/users/dvhart/linux.git/shortlog/refs/heads/futex/f
utex-lock/v7
I can work on forward porting this series to current mainline (post recent
security fixes) and cleaning up the commentary and such if people are
interested in seeing this implementation (based on Peter Z's spinning
mutex work iirc) resurrected...
No. We really want to avoid more magic hackery in the futex code.
Lets sit down and think about what we need:
1) Support for all existing features
2) More fine grained locking
3) Optimistic spinning
@1: No discussion about that. Period.
We are not going to introduce some new futex opcode, which is
optimized for a microbenchmark and ignoring all of the pain we
went through in the last 10 years. No way, especially after the
recent security disaster.
@2 and @3: Yes, we want that.
But again, we don't add fine grained locking just for some half
baken new opcode. No, we are adding it where it makes the most
sense and lets us reuse most of the code.
I can predict your question, how that should work :)
If we want to have fine grained locking beyond the futex hash
buckets and that's something we discussed before, you need a state
representation of the user space futex in the kernel. That's what
Waiman added as well, just in a way that's beyond repair.
The charm of the futex hash buckets is that they do not create
kernel state because the futex_q which is enqueued into the bucket
is on the task stack of the task which is blocked on the futex.
So much for the theory, because that stopped to be true when we
added support for PI futexes. They already create kernel internal
state which is not magically removed when the thread exits the
syscall. It's called pi_state.
Now the question is how is this related to the non PI magic
spinning optimization? Very much so.
Simply because the handling of pi_state already covers ALL the
corner cases which come with the extra kernel internal state and
they provide the full function set of futexes required by the
various (ab)use cases including the requeue functionality which is
required for condvars. It even supports caching of the pi_state
struct in a way which makes sense, rather than blindly slapping a
cached entry onto each hash bucket.
So it's not a really mind boggling thought experiment to think
about this magic new feature as a subset of the already existing
PI futex code. It is a subset, just minus the PI portion plus the
more fine grained locking.
So the right solution is to rework the existing code.
1) Make pi_state the entity which gets enqueued into the hash bucket
and manage the waiters in a pi_state internal queue.
Straight forward problem as it is still protected by the hash
bucket lock.
2) Add private locking to the pi_state to reduce the lock contention
on the hash bucket lock.
Straight forward conversion as well
3) Make mutex a subset of rt_mutex
That makes a lot of sense, simply because a mutex is the same as a
rtmutex just without the PI part.
Just for the record before anyone cries murder: The original mutex
implemention was modeled after the rtmutex one in the first place
and the optimistic spinning was first introduced on rtmutexes by
Gregory Haskins et. al. in the context of the RT tree. Back then it
was too early or we were simply too stupid to see the similarities
and opted for a complete separate implementation.
Yes, I'm aware that this is a non-trivial problem, but if you look
at the details, then the non-trivial part is in the slow path were
stuff actually goes to sleep. The fast path of mutex and rt_mutex
is simply the same. So there is no reason to keep them separate. An
extra conditional in the slow path is not going to hurt at all.
Surely, you might say, that I'm an egoistic bastard, who just wants
to have the benefit of MCS for rtmutex for free. Right you are, but
there is a whole bunch of reasons why this makes tons of sense:
- As I said above, it's almost the same, except for the slow path
details, where a few extra conditionals do not matter
- Sharing the code has the obvious benefits. And it's not only
sharing between rtmutex and mutex, it's also sharing the
underlying optimizations of MCS for the kernel internal users and
the user space exposed ones, i.e. futexes.
- Once unified the desired futex functionality just works with a
minimal impact on the futex code itself.
The futex code does not care whether the underlying primitive has
PI semantics or not, it just cares that all the required features
like proxy locking etc. are in place. And that everything like
timeouts, requeue etc. is just supported.
- The semantics of the new futex functionality has not to be
defined again. We can simply reuse the rather well defined and
well tested straight forward semantics of the existing PI
opcodes.
- That minimizes the risk massively, because all state and error
handling is common code.
- Any update to the underlying primitives will benefit ALL usage
sites and reduces the copy and paste induced hell of MCS code
sprinkled all over the kernel.
4) Enable user space to make use of it.
Whether this will be a separate opcode or just a new flag to the
existing PI opcodes is going to be just a bikeshedding question at
that point. :)
The important point is, that we do NOT grow any new unmaintainable
warts to the futex code. And the 650+ new lines of hackery which come
with the proposed patch set are in no way acceptable, especially as
they only cover the minimalistic functionality set of futexes. Not to
talk about the other issues I've observed on the first glance.
So before anyone comes up with a "solution" for all of this tomorrow
afternoon in form of another half baken patch, please sit back mull it
in your head and lets have a proper discussion about the approach
first.
Thanks,
tglx
Thank for your thorough analysis and suggestions on what to do to support spinning futexes. You certainly know more about the internal working of futex than most of us. I can live with what you have suggested. My patch is just a proof of concept piece to demonstrate optimistic spinning on futex is something worthwhile to do. I think I have achieved my goal of stirring interest in this area. My next step will be to look into the direction of what you have suggested and figure out what actual code changes will be needed.
Thank again for your help.
-Longman
From: Waiman Long <hidden> Date: 2014-07-22 20:25:25
On 07/22/2014 05:59 AM, Thomas Gleixner wrote:
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
quoted
On Tue, Jul 22, 2014 at 10:39:17AM +0200, Thomas Gleixner wrote:
quoted
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
quoted
Anyway, there is one big fail in the entire futex stack that we 'need'
to sort some day and that is NUMA. Some people (again database people)
explicitly do not use futexes and instead use sysvsem because of this.
The problem with numa futexes is that because they're vaddr based there
is no (persistent) node information. You always end up having to fall
back to looking in all nodes before you can guarantee there is no
matching futex.
One way to achieve it is by extending the futex value to include a node
number, but that's obviously a complete ABI break. Then again, it should
be pretty straight fwd, since the node number doesn't need to be part of
the actual atomic update part, just part of the userspace storage.
So you want per node hash buckets, right? Fair enough, but how do you
make sure, that no thread/process on a different node is fiddling with
that "node bound" futex as well?
You don't and that should work just as well, just slower. But since the
node id is in the futex 'value' we'll always end up in the right
node-hash, even if its a remote one.
So yes, per node hashes, and a persistent futex->node map.
Which works fine as long as you only have the futex_q on the stack of
the blocked task. If user space is lying to you, then you just end up
with a bunch of threads sleeping forever. Who cares?
But if you create independent kernel state, which we have with
pi_state and which you need for finegrained locking and further
spinning fun, you open up another can of worms. Simply because this
would enable rogue user space to create multiple instances of the
kernel internal state. I can predict the CVEs resulting from that
even without using a crystal ball.
Thanks,
tglx
I think NUMA futex, if implemented, is a completely independent piece that have no direct relationship with optimistic spinning futex. It should be a separate patch and not mixing with optimistic spinning patch which will only make the latter one more complicated.
-Longman
From: Thomas Gleixner <hidden> Date: 2014-07-22 20:53:10
On Tue, 22 Jul 2014, Waiman Long wrote:
On 07/22/2014 05:59 AM, Thomas Gleixner wrote:
quoted
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
quoted
On Tue, Jul 22, 2014 at 10:39:17AM +0200, Thomas Gleixner wrote:
quoted
On Tue, 22 Jul 2014, Peter Zijlstra wrote:
quoted
Anyway, there is one big fail in the entire futex stack that we 'need'
to sort some day and that is NUMA. Some people (again database people)
explicitly do not use futexes and instead use sysvsem because of this.
The problem with numa futexes is that because they're vaddr based
there
is no (persistent) node information. You always end up having to fall
back to looking in all nodes before you can guarantee there is no
matching futex.
One way to achieve it is by extending the futex value to include a
node
number, but that's obviously a complete ABI break. Then again, it
should
be pretty straight fwd, since the node number doesn't need to be part
of
the actual atomic update part, just part of the userspace storage.
So you want per node hash buckets, right? Fair enough, but how do you
make sure, that no thread/process on a different node is fiddling with
that "node bound" futex as well?
You don't and that should work just as well, just slower. But since the
node id is in the futex 'value' we'll always end up in the right
node-hash, even if its a remote one.
So yes, per node hashes, and a persistent futex->node map.
Which works fine as long as you only have the futex_q on the stack of
the blocked task. If user space is lying to you, then you just end up
with a bunch of threads sleeping forever. Who cares?
But if you create independent kernel state, which we have with
pi_state and which you need for finegrained locking and further
spinning fun, you open up another can of worms. Simply because this
would enable rogue user space to create multiple instances of the
kernel internal state. I can predict the CVEs resulting from that
even without using a crystal ball.
Thanks,
tglx
I think NUMA futex, if implemented, is a completely independent piece that
have no direct relationship with optimistic spinning futex. It should be a
separate patch and not mixing with optimistic spinning patch which will only
make the latter one more complicated.
Bullshit. Of course it handles separate issues, but Peter is
completely right, that the NUMA aspect is a far bigger issue than the
optimistic spinning stuff. Do you have an idea what the costs of cross
node memory access and cacheline bouncing are? Obviously not, as you
only interest seems to be to slap optimistic spinning to every place
which deals with locking.
And if you had tried to read _AND_ understand the discussion above,
you might have noticed that providing NUMA awareness requires a lot of
the functionality which is needed for optimistic spinning as well.
But no, you did not even take the time to think about it, you just
claim that it makes your optimistic stuff more complicated. Just get
it, there is a world outside of optimistic spinning.
Thanks,
tglx
From: Thomas Gleixner <hidden> Date: 2014-07-22 21:03:47
On Tue, 22 Jul 2014, Waiman Long wrote:
On 07/21/2014 09:01 PM, Thomas Gleixner wrote:
quoted
So before anyone comes up with a "solution" for all of this tomorrow
afternoon in form of another half baken patch, please sit back mull it
in your head and lets have a proper discussion about the approach
first.
Thanks,
tglx
Thank for your thorough analysis and suggestions on what to do to support
spinning futexes. You certainly know more about the internal working of futex
than most of us. I can live with what you have suggested. My patch is just a
proof of concept piece to demonstrate optimistic spinning on futex is
something worthwhile to do. I think I have achieved my goal of stirring
We knew that already as Darren has proven that optimistic spinning in
a simpler form provides a huge benefit. So you do not have achieved
anything except annoying people with your sloppiness.
interest in this area. My next step will be to look into the direction of what
you have suggested and figure out what actual code changes will be needed.
You really can do what you want with your time. You can either reread
AND understand the paragraph, which I left as a quote from my previous
mail, AND act acoordingly or just stay away from futex.c.
Thanks,
tglx