lkml.org 
[lkml]   [2008]   [May]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Subject[PATCH 0/3] 64-bit futexes: Intro
This patch series adds support for 64-bit futexes.  The current futexes
only protect 32-bits. I don't know why, ask the original authors. It is
unnecessarily limiting, though, especially for 64-bit machines.

To understand the problem let me just say that futexes work by storing
a program-defined state in a variable. Threads then can wait for the
state of the variable to change. It all works dandy if the protocol for
using futexes is followed correctly; see

http://people.redhat.com/drepper/futexes.pdf

For mutexes, semaphores etc this is quite easy. For mutexes, for instance,
we have as state to protect a flag whether the mutex is locked and whether
there is any thread waiting for the release. This can be done easily with
the available 32 bits in a futex.

The situation is different for more complex synchronization objects. The
best example are reader/writer locks. Here the state consists at least
of

- number of readers which locked the rwlock
- flag whether rwlock is locked for reader, writing, or not at all
- number of readers waiting
- number of writers waiting

I.e., rwlocks are significantly more complicated. Much of the complication
stems from the requirement to have to types: those which prefer readers and
those which prefer writers.

Without imposing unreasonable limitations on the number of concurrent users
a rwlock can have the state cannot be represented in a single 32-bit variable.
This is why the current rwlock implementation uses an internal lock and
spreads the state out in several variables.

This works, but there is a significant performance penalty to be paid:

- at least two atomic operations to lock and unlock the internal lock
- multiple readers are not really able to run concurrently since they
might block on the internal lock
- following from the last point, the behaviour of the code is less
predictable due to scheduling artifacts


The logical solution is to extend the size of the state which can be
protected by allowing 64-bit futexes on architectures which can support
them. This is not new. The last time it was brought in

http://lkml.org/lkml/2007/3/21/65

but nothing happened. I must admit that I didn't follow thorugh myself.

Anyway, I finally bit the bullet and wrote a patch myself. It differs
from the old patch:

- FUTEX_64_FLAG is a flag to the existing syscall, not a new syscall.
Given the changes which are needed the latter would have been overkill
IMO

- no 64-bit support for the PI variants. It simply makes no sense. The
value of the variables protected by the PI variants is under control of
the kernel and it's always a TID. Those are 32-bit values.

As you can see and the first patch the required changes really aren't that
many. A large part of the patch deals with changing the interface of the
futex_atomic_op_inuser function. The additional parameter is simply
ignored if 64-bit futexes aren't supported.

The patch also goes to great length to avoid negative impact for
archictectures which do not have 64-bit futexes. You can see several
if-expressions which are decided at compile-time, optimizing out all the
additional code.

Finally, enabling 64-bit futexes for 64-bit architectures is quite simple.
The second patch enables them for x86-64. Most of the new lines are simply
copies of the inline asms used for the 32-bit futexes, adapted for 64-bit
operations.

As for 32-bit architectures, they are mostly out of luck. That's OK, all
the code still works as before, it's just slower. The exception is perhaps
x86. x86 has the cmpxchg8b instruction for many years now. This is why
I added enablement for 64-bit futexes for x86 as well. It's a bit more
complicated and it requires a new system call. The reason is obvious: the
existing system call takes 32-bit values for the value parameters. On
64-bit machines these are in any case 64-bit values, so passing 64-bit
values only requires a change to the function parameter type. For 32-bit
machines it is not that easy, hence the new system call. To make things
even more interesting, the required additional parameter pushes us beyond
the 6 parameter limit and the parameters have to be passed down in memory.
Nothing new.


Anyway, is it all worth it? Well, here's a measurement of a workload
similar for what customers of our are using. These are raw numbers,
for a reason:

# Old New Gain
threads Rwlocks Rwlocks

1 4,991,633,560 3,986,898,840 20.13%
2 14,187,564,600 5,080,538,220 64.19%
3 20,727,416,260 5,291,971,820 74.47%
4 23,079,608,650 6,652,036,830 71.18%
5 23,1766,32,860 6,570,373,500 71.65%
6 21,913,357,010 6,591,716,100 69.92%
7 22,975,750,700 6,597,761,790 71.28%
8 22,349,919,860 6,632,005,730 70.33%
9 24,784,438,890 6,599,062,590 73.37%
10 24,899,243,380 6,493,066,340 73.92%
11 25,358,788,130 6,735,662,240 73.44%
12 19,955,548,890 6,591,059,500 66.97%
13 24,058,349,440 6,709,288,100 72.11%
14 26,002,901,340 6,741,505,130 74.07%
15 19,790,724,570 6,720,973,690 66.04%
16 26,639,730,750 6,558,662,430 75.38%

The test is run on a uni-processor quad core machine. The task is run with
varying number of threads. In this example the actual work performed is
trivial. In other words, the overhead for the locking is quite large. I
have put the data in a graph:

http://people.redhat.com/drepper/newrwlock.png

What is obvious is that with the new implementation to uncontended case
is 20% faster. That alone should be a good reason. But as can be seen
it get even better with a large number of threads. It peaks when four
threads are used (== number of cores) but I still show the results for
more threads to point out the better predictability. These are the
minimum values from ten runs each, no averaging. The old code, due to
the use of the internal lock, causes a lotter of jitters in the times,
reducing predictability. In term of performance, the new code is about
four times faster on this workload. It's certainly not characteristic
but I haven't seen a workload where the new code is slower.

I also haven't seen any case where the additional overhead in the futex
system call implementation is noticeable.

I tested the code extensively on a number of x86-64 machines, from small
dual cores machines to quad socket/quad cores machines. I'm even using
it on my main workstation right now.

The three patches can be applied individually and everything should
continue to work fine. The patches apply to Linus' current tree.


\
 
 \ /
  Last update: 2008-05-31 03:31    [W:0.085 / U:2.720 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site