[1/2] lib: Provide generic atomic64_t implementation

Many processor architectures have no 64-bit atomic instructions, but
we need atomic64_t in order to support the perf_counter subsystem.

This adds an implementation of 64-bit atomic operations using hashed
spinlocks to provide atomicity.  For each atomic operation, the address
of the atomic64_t variable is hashed to an index into an array of 16
spinlocks.  That spinlock is taken (with interrupts disabled) around the
operation, which can then be coded non-atomically within the lock.

On UP, all the spinlock manipulation goes away and we simply disable
interrupts around each operation.  In fact gcc eliminates the whole
atomic64_lock variable as well.

Signed-off-by: Paul Mackerras <paulus@samba.org>
---
Linus, Andrew: OK if this goes in via the powerpc tree?

 include/asm-generic/atomic64.h |   42 ++++++++++
 lib/Kconfig                    |    6 ++
 lib/Makefile                   |    2 +
 lib/atomic64.c                 |  175 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 225 insertions(+), 0 deletions(-)
 create mode 100644 include/asm-generic/atomic64.h
 create mode 100644 lib/atomic64.c

On Sat, 13 Jun 2009, Paul Mackerras wrote:
>
> Linus, Andrew: OK if this goes in via the powerpc tree?

Ok by me.

		Linus

On Sat, 13 Jun 2009, Linus Torvalds wrote:
> 
> On Sat, 13 Jun 2009, Paul Mackerras wrote:
> >
> > Linus, Andrew: OK if this goes in via the powerpc tree?
> 
> Ok by me.

Btw, do 32-bit architectures really necessarily want 64-bit performance 
counters? 

I realize that 32-bit counters will overflow pretty easily, but I do 
wonder about the performance impact of doing things like hashed spinlocks 
for 64-bit counters. Maybe the downsides of 64-bit perf counters on such 
architectures might outweight the upsides?

		Linus

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Sat, 13 Jun 2009, Linus Torvalds wrote:
> > 
> > On Sat, 13 Jun 2009, Paul Mackerras wrote:
> > >
> > > Linus, Andrew: OK if this goes in via the powerpc tree?
> > 
> > Ok by me.
> 
> Btw, do 32-bit architectures really necessarily want 64-bit 
> performance counters?
> 
> I realize that 32-bit counters will overflow pretty easily, but I 
> do wonder about the performance impact of doing things like hashed 
> spinlocks for 64-bit counters. Maybe the downsides of 64-bit perf 
> counters on such architectures might outweight the upsides?

We account all sorts of non-hw bits via atomic64_t as well - for 
example time related counters in nanoseconds - which wrap 32 bits at 
4 seconds.

There's also security/stability relevant bits:

        counter->id             = atomic64_inc_return(&perf_counter_id);

We dont really want that ID to wrap ever - it could create a leaking 
of one PMU context into another. (We could rewrite it by putting a 
global lock around it, but still - this is a convenient primitive.)

In select places we might be able to reduce the use of atomic64_t 
(that might make performance sense anyway) - but to get rid of all 
of them would be quite painful. We initially started with a 32-bit 
implementation and it was quite painful with fast-paced units.

So since Paul has already coded the wrappers up ... i'd really 
prefer that, unless there's really compelling reasons not to do it.

	Ingo

On Saturday 13 June 2009, Paul Mackerras wrote:
> +extern long long atomic64_read(const atomic64_t *v);
> +extern void     atomic64_set(atomic64_t *v, long long i);
> +extern void     atomic64_add(long long a, atomic64_t *v);
> +extern long long atomic64_add_return(long long a, atomic64_t *v);
> +extern void     atomic64_sub(long long a, atomic64_t *v);
> +extern long long atomic64_sub_return(long long a, atomic64_t *v);
> +extern long long atomic64_dec_if_positive(atomic64_t *v);
> +extern long long atomic64_cmpxchg(atomic64_t *v, long long o, long long n);
> +extern long long atomic64_xchg(atomic64_t *v, long long new);
> +extern int      atomic64_add_unless(atomic64_t *v, long long a, long long u);
> +
> +#define atomic64_add_negative(a, v)    (atomic64_add_return((a), (v)) < 0)
> +#define atomic64_inc(v)                        atomic64_add(1LL, (v))
> +#define atomic64_inc_return(v)         atomic64_add_return(1LL, (v))
> +#define atomic64_inc_and_test(v)       (atomic64_inc_return(v) == 0)
> +#define atomic64_sub_and_test(a, v)    (atomic64_sub_return((a), (v)) == 0)
> +#define atomic64_dec(v)                        atomic64_sub(1LL, (v))
> +#define atomic64_dec_return(v)         atomic64_sub_return(1LL, (v))
> +#define atomic64_dec_and_test(v)       (atomic64_dec_return((v)) == 0)
> +#define atomic64_inc_not_zero(v)       atomic64_add_unless((v), 1LL, 0LL)
> +

How about also doing these:?

#define atomic64_sub(a, v)		atomic64_add(-a, v)
#define atomic64_sub_return(a, v)	atomic64_add_return(-a, v)
#define atomic64_add(a, v)		(void)atomic64_add_return(a, v)

The cost to the caller (one or two instruction per call site)
seems to be about the same as for the other wrapper macros.

	Arnd <><

Linus Torvalds wrote:
> On Sat, 13 Jun 2009, Linus Torvalds wrote:
>   
>> On Sat, 13 Jun 2009, Paul Mackerras wrote:
>>     
>>> Linus, Andrew: OK if this goes in via the powerpc tree?
>>>       
>> Ok by me.
>>     
>
> Btw, do 32-bit architectures really necessarily want 64-bit performance 
> counters? 
>
> I realize that 32-bit counters will overflow pretty easily, but I do 
> wonder about the performance impact of doing things like hashed spinlocks 
> for 64-bit counters. Maybe the downsides of 64-bit perf counters on such 
> architectures might outweight the upsides?
>   

An alternative implementation using 64-bit cmpxchg will recover most of 
the costs of hashed spinlocks.  I assume most serious 32-bit 
architectures have them?

Avi Kivity writes:

> An alternative implementation using 64-bit cmpxchg will recover most of 
> the costs of hashed spinlocks.  I assume most serious 32-bit 
> architectures have them?

Have a 64-bit cmpxchg, you mean?  x86 is the only one I know of, and
it already has an atomic64_t implementation using cmpxchg8b (or
whatever it's called).

My thinking is that the 32-bit non-x86 architectures will be mostly
UP, so the overhead is just an interrupt enable/restore.  Those that
are SMP I would expect to be small SMP -- mostly just 2 cpus and maybe
a few 4-way systems.

Paul.

Paul Mackerras wrote:
> Avi Kivity writes:
>
>   
>> An alternative implementation using 64-bit cmpxchg will recover most of 
>> the costs of hashed spinlocks.  I assume most serious 32-bit 
>> architectures have them?
>>     
>
> Have a 64-bit cmpxchg, you mean?  x86 is the only one I know of, and
> it already has an atomic64_t implementation using cmpxchg8b (or
> whatever it's called).
>   

Yes (and it is cmpxchg8b).  I'm surprised powerpc doesn't have DCAS support.

> My thinking is that the 32-bit non-x86 architectures will be mostly
> UP, so the overhead is just an interrupt enable/restore.  Those that
> are SMP I would expect to be small SMP -- mostly just 2 cpus and maybe
> a few 4-way systems.
>   

The new Nehalems provide 8 logical threads in a single socket.  All 
those threads share a cache, and they have cmpxchg8b anyway, so this 
won't matter.

> The new Nehalems provide 8 logical threads in a single socket.  All
 > those threads share a cache, and they have cmpxchg8b anyway, so this
 > won't matter.

FWIW, Nehalem EX actually goes to 8 cores/16 threads per socket.  But
worrying about 32-bit performance on Nehalem is a little silly -- this
simplest solution is simply to run a 64-bit kernel.

 - R.

Roland Dreier writes:

> FWIW, Nehalem EX actually goes to 8 cores/16 threads per socket.  But
> worrying about 32-bit performance on Nehalem is a little silly -- this
> simplest solution is simply to run a 64-bit kernel.

I'm not worried about ANY x86 processor, 32-bit or 64-bit, in fact,
since x86 already has an atomic64_t implementation for both 32-bit and
64-bit.

It is interesting, though, that arch/x86/include/asm/atomic_32.h
unconditionally uses cmpxchg8b to implement atomic64_t, but I thought
that cmpxchg8b didn't exist in processors prior to the Pentium.
Presumably you can't use perf_counters on a 386 or 486.

Paul.

On Sun, Jun 14, 2009 at 04:04:36PM +0300, Avi Kivity wrote:
> Paul Mackerras wrote:
>> Avi Kivity writes:
>>
>>   
>>> An alternative implementation using 64-bit cmpxchg will recover most 
>>> of the costs of hashed spinlocks.  I assume most serious 32-bit  
>>> architectures have them?
>>>     
>>
>> Have a 64-bit cmpxchg, you mean?  x86 is the only one I know of, and
>> it already has an atomic64_t implementation using cmpxchg8b (or
>> whatever it's called).
>>   
>
> Yes (and it is cmpxchg8b).  I'm surprised powerpc doesn't have DCAS support.

Well, s390 and m68k have the equivalent (although I don't think Linux
suppiorts SMP m68k, although some dual 68040/68060 boards have existed).

But 32 bit PPC will never have it. It just does not fit in the architecture
since integer loads and stores are limited to 32 bit (or split into 32 bit
chunks). Besides that there is no instruction that performs a read-modify-write
of memory. This would make the LSU much more complex for a corner case.

Hey, Intel also botched the first implementation of cmpxchg8b on the Pentium:
the (in)famous f00f bug is actually "lock cmpxchg8b" with a register operand.

Now for these counters, other solutions could be considered, like using
the most significant bit as a lock and having "only" 63 usable bits (when 
counting ns, this overflows at 292 years). 

>
>> My thinking is that the 32-bit non-x86 architectures will be mostly
>> UP, so the overhead is just an interrupt enable/restore.  Those that
>> are SMP I would expect to be small SMP -- mostly just 2 cpus and maybe
>> a few 4-way systems.
>>   
>
> The new Nehalems provide 8 logical threads in a single socket.  All  
> those threads share a cache, and they have cmpxchg8b anyway, so this  
> won't matter.
>

The problem is not Nehalem (who wants to run 32 bit kernels on a Nehalem
anyway) or x86.

The problem is that the assumption that the largest PPC32 SMP are 4 way
may be outdated:

http://www.freescale.com/webapp/sps/site/prod_summary.jsp?fastpreview=1&code=P4080

and some products including that processor have been announced (I don't know
whether they are shipping or not) and (apparently) run Linux.

	Gabriel

On Sat, Jun 13, 2009 at 03:10, Paul Mackerras wrote:
> +typedef struct {
> +       long long counter;
> +} atomic64_t;

lack of volatile seems odd compared to:
include/linux/types.h:
typedef struct {
    volatile int counter;
} atomic_t;
-mike

On Thu, 2009-06-18 at 19:55 -0400, Mike Frysinger wrote:
> On Sat, Jun 13, 2009 at 03:10, Paul Mackerras wrote:
> > +typedef struct {
> > +       long long counter;
> > +} atomic64_t;
> 
> lack of volatile seems odd compared to:
> include/linux/types.h:
> typedef struct {
>     volatile int counter;
> } atomic_t;

Since the counter is only accessed within a spinlock, the volatile
wouldn't be very useful here.

Cheers,
Ben.

Mike Frysinger writes:

> On Sat, Jun 13, 2009 at 03:10, Paul Mackerras wrote:
> > +typedef struct {
> > +       long long counter;
> > +} atomic64_t;
> 
> lack of volatile seems odd compared to:
> include/linux/types.h:
> typedef struct {
>     volatile int counter;
> } atomic_t;
> -mike

It's only accessed under a spinlock, so I don't think it needs to be
volatile.  On UP it's accessed within local_irq_save/restore which
should also be compiler barriers and prevent memory access reordering,
so again volatile isn't needed.

Paul.

On Thu, Jun 18, 2009 at 20:47, Paul Mackerras wrote:
> Mike Frysinger writes:
>> On Sat, Jun 13, 2009 at 03:10, Paul Mackerras wrote:
>> > +typedef struct {
>> > +       long long counter;
>> > +} atomic64_t;
>>
>> lack of volatile seems odd compared to:
>> include/linux/types.h:
>> typedef struct {
>>     volatile int counter;
>> } atomic_t;
>
> It's only accessed under a spinlock, so I don't think it needs to be
> volatile.  On UP it's accessed within local_irq_save/restore which
> should also be compiler barriers and prevent memory access reordering,
> so again volatile isn't needed.

i'm not suggesting it is needed, i'm saying it's a bit confusing.  a
simple comment above the atomic64_t type with your simple explanation
here would go a long way.
-mike