Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1370201 > unrolled thread

Re: [RFC patch 4/7] futex: Add support for attached futexes

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC patch 4/7] futex: Add support for attached futexes Ingo Molnar <mingo@kernel.org> - 2016-04-03 13:20 +0200
    Re: [RFC patch 4/7] futex: Add support for attached futexes Linus Torvalds <torvalds@linux-foundation.org> - 2016-04-03 13:40 +0200
      Re: [RFC patch 4/7] futex: Add support for attached futexes Torvald Riegel <triegel@redhat.com> - 2016-04-05 09:50 +0200
      Re: [RFC patch 4/7] futex: Add support for attached futexes Carlos O'Donell <carlos@redhat.com> - 2016-04-05 18:00 +0200

#1370201 — Re: [RFC patch 4/7] futex: Add support for attached futexes

* Thomas Gleixner <tglx@linutronix.de> wrote:

> The standard futex mechanism in the Linux kernel uses a global hash to store
> transient state. Collisions on that hash can lead to performance degradation
> and on real-time enabled kernels even to priority inversions.
> 
> To guarantee futexes without collisions on the global kernel hash, we provide
> a mechanism to attach to a futex. This creates futex private state which
> avoids hash collisions and on NUMA systems also cross node memory access.
> 
> To utilize this mechanism each thread has to attach to the futex before any
> other operations on that futex.
> 
> The inner workings are as follows:
> 
> Attach:
> 
>     sys_futex(FUTEX_ATTACH | FUTEX_ATTACHED, uaddr, ....);
> 
>     If this is the first attach to uaddr then a 'global state' object is
>     created. This global state contains a futex hash bucket and a futex_q
>     object which is enqueued into the global hash for reference so subsequent
>     attachers can find it. Each attacher takes a reference count on the
>     'global state' object and hashes 'uaddr' into a thread local hash. This
>     thread local hash is lock free and dynamically expanded to avoid
>     collisions. Each populated entry in the thread local hash stores 'uaddr'
>     and a pointer to the 'global state' object.
> 
> Futex ops:
> 
>     sys_futex(FUTEX_XXX | FUTEX_ATTACHED, uaddr, ....);
> 
>     If the attached flag is set, then 'uaddr' is hashed and the thread local
>     hash is checked whether the hash entry contains 'uaddr'. If no, an error
>     code is returned. If yes, the hash slot number is stored in the futex key
>     which is used for further operations on the futex. When the hash bucket is
>     looked up then attached futexes will use the slot number to retrieve the
>     pointer to the 'global state' object and use the embedded hash bucket for
>     the operation. Non-attached futexes just use the global hash as before.
> 
> Detach:
> 
>     sys_futex(FUTEX_DETACH | FUTEX_ATTACHED, uaddr, ....);
>    
>     Detach removes the entry in the thread local hash and decrements the
>     refcount on the 'global state' object. Once the refcount drops to zero the
>     'global state' object is removed from the global hash and destroyed.
> 
>     Thread exit cleans up the thread local hash and the 'global state' objects
>     as we do for other futex related storage already.
> 
> The thread local hash and the 'global state' object are allocated on the node
> on which the attaching thread runs.
> 
> Attached mode works with all futex operations and with both private and shared
> futexes. For operations which involve two futexes, i.e. FUTEX_REQUEUE_* both
> futexes have to be either attached or detached (like FUTEX_PRIVATE).
> 
> Why not auto attaching?
> 
>     Auto attaching has the following problems:
> 
>      - Memory consumption
>      - Life time issues
>      - Performance issues due to the necessary allocations

But those are mostly setup only costs, right?

So I don't think this conclusion is necessarily true, even on smaller systems:

>     So, no. It must be opt-in and reserved for explicit isolation purposes.
> 
> A modified version of 'perf bench futex hash' shows the following results:

and look at the very measurable performance advantages on a small NUMA system:

  Before:

  >  Averaged 1451441 operations/sec (+- 3.65%), total secs = 60

  After:

  >  Averaged 1709712 operations/sec (+- 4.67%), total secs = 60

  > That's a performance increase of 18%.

... and I suspect that on a larger NUMA system the speedup is probably a lot more 
pronounced.

Also, the thing is, allocation/deallocation costs are a second order concern IMHO, 
because most of the futex's usage is the lock/unlock operations.

So my prediction: in real life large systems will want to have collision-free 
futexes most of the time, and they don't want to modify every futex using 
application or library. So this is a mostly kernel side system sizing 
question/decision, not really a user-side system purpose policy question.

So an ABI distinction and offloading the decision to every single application that 
wants to use it and hardcode it into actual application source code via an ABI is 
pretty much the _WORST_ way to go about it IMHO...

So how about this: don't add any ABI details, but make futexes auto-attached on 
NUMA systems (and obviously PREEMPT_RT systems)?

I.e. make it a build time or boot time decision at most, don't start a messy 
'should we used attached futexes or not' decisions on the ABI side, which we know 
from Linux ABI history won't be answered and utilized very well by applications!

Thanks,

	Ingo

[toc] | [next] | [standalone]

#1370202

On Sun, Apr 3, 2016 at 6:16 AM, Ingo Molnar <mingo@kernel.org> wrote:
>
> So an ABI distinction and offloading the decision to every single application that
> wants to use it and hardcode it into actual application source code via an ABI is
> pretty much the _WORST_ way to go about it IMHO...
>
> So how about this: don't add any ABI details, but make futexes auto-attached on
> NUMA systems (and obviously PREEMPT_RT systems)?

I agree.

Do *not* make this a visible new ABI.

You will find that people will make exactly the wrong choices - either
not using it (because the futex is deep in a standard library!) when
they want to, or using it when they shouldn't (because the futex is
deep in a standard library, and the library writer knows *his* code is
so important that it should get a special faster futex).

So I absolutely detest this approach. It's the wrong way to go about
things. User space does *not* know whether they want to use this or
not, and they *will* be wrong.

So automatically using a local hashtable (for private mutexes - I
think people need to just accept that a shared mutex is more costly)
according to some heuristic is definitely the way to go. And yes, the
heuristic may be well be - at least to start - "this is a preempt-RT
system" (for people who clearly care about having predictable
latencies) or "this is actually a multi-node NUMA system, and I have
heaps of memory".

Then, add a tunable (for root, not per-futex) to allow people to tweak it.

Because the *last* thing you want is programmerrs saying "I'm so
important that I want the special futex". Because every single
programmer thinks they are special and that _their_ code is special. I
know - because I'm special.

                   Linus

[toc] | [prev] | [next] | [standalone]

#1371290

On Sun, 2016-04-03 at 06:30 -0500, Linus Torvalds wrote:
> On Sun, Apr 3, 2016 at 6:16 AM, Ingo Molnar <mingo@kernel.org> wrote:
> >
> > So an ABI distinction and offloading the decision to every single application that
> > wants to use it and hardcode it into actual application source code via an ABI is
> > pretty much the _WORST_ way to go about it IMHO...
> >
> > So how about this: don't add any ABI details, but make futexes auto-attached on
> > NUMA systems (and obviously PREEMPT_RT systems)?
> 
> I agree.
> 
> Do *not* make this a visible new ABI.

From a glibc perspective, I agree that this shouldn't require an
extension of the ABI unless it's really the only possible way to solve
this.

For "special" mutex kinds such as PI mutexes, the change in the
interface might be justifiable -- but for ordinary mutexes, there's no
good place to add the attach/detach calls in each thread: An
implementation of, say, C11 mutexes cannot easily estimate whether it
should use attached futexes, and it would have to track whether a
particular mutex has been attached to by the current thread; this might
just move the overhead of tracking and caching associations from the
kernel to userspace.

> You will find that people will make exactly the wrong choices - either
> not using it (because the futex is deep in a standard library!) when
> they want to, or using it when they shouldn't (because the futex is
> deep in a standard library, and the library writer knows *his* code is
> so important that it should get a special faster futex).

There are cases where userspace might know that it should use a
"special" futex.  Consider an MCS-lock implementation in glibc by which
all pthreads, C, and C++ mutexes are backed: the lock nodes that threads
would be spinning on would be per-thread and exist for the whole
lifetime of the thread; attach and detach would be simple to do, and
there would be a limited number of these in the system.
A Java VM's park/unpark implementation might be another candidate.
However, these use cases are pretty specific (eg, there's only a single
waiter), so any kernel support for these might be more special too.

[toc] | [prev] | [next] | [standalone]

#1371748

On 04/03/2016 07:30 AM, Linus Torvalds wrote:
> On Sun, Apr 3, 2016 at 6:16 AM, Ingo Molnar <mingo@kernel.org> wrote:
>>
>> So an ABI distinction and offloading the decision to every single application that
>> wants to use it and hardcode it into actual application source code via an ABI is
>> pretty much the _WORST_ way to go about it IMHO...
>>
>> So how about this: don't add any ABI details, but make futexes auto-attached on
>> NUMA systems (and obviously PREEMPT_RT systems)?
> 
> I agree.
> 
> Do *not* make this a visible new ABI.

Agreed.

We had similar requests in glibc to add APIs to tweak the parameters of
the elision for locks backed by hardware transactional memory.

The person submitting the patches always thinks this is a great API
because it allows them to write tests to verify their own work (which
means it still might be useful for internal testing or developing
auto-tuning).

Users have no clue what to do with the API and worse the state space of
the parameters is immense. You can't possibly do any kind of sensible
optimization without knowing a lot about the hardware.

So no public API was ever added in glibc for pthread_mutex_lock elision
parameters. Either the parameters work by default or you have to post
patches to change the auto-tuning used internally in glibc.

> So automatically using a local hashtable (for private mutexes - I
> think people need to just accept that a shared mutex is more costly)
> according to some heuristic is definitely the way to go. And yes, the
> heuristic may be well be - at least to start - "this is a preempt-RT
> system" (for people who clearly care about having predictable
> latencies) or "this is actually a multi-node NUMA system, and I have
> heaps of memory".

Agreed.
 
> Then, add a tunable (for root, not per-futex) to allow people to tweak it.

Agreed.

-- 
Cheers,
Carlos.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web