[PATCH] atomic_inc_return() for i386[1/5] (Re: atomic_inc_return)

[PATCH] atomic_inc_return() for i386[1/5] (Re: atomic_inc_return)

[Kaigai Kohei]

[1/5] atomic_inc_return-linux-2.6.9-rc1.i386.patch
  This patch implements atomic_inc_return() and so on for i386,
  and includes runtime check whether CPU is legacy 386.
  It is same as I posted to LKML and Andi Kleen at '04/09/01.

Signed-off-by: KaiGai, Kohei <kaigai@ak.jp.nec.com>
--------
Kai Gai <kaigai@ak.jp.nec.com>


diff -rNU4 linux-2.6.9-rc1/include/asm-i386/atomic.h linux-2.6.9-rc1.atomic_inc_return/include/asm-i386/atomic.h
--- linux-2.6.9-rc1/include/asm-i386/atomic.h	2004-08-24 16:02:24.000000000 +0900
+++ linux-2.6.9-rc1.atomic_inc_return/include/asm-i386/atomic.h	2004-09-10 10:15:18.000000000 +0900
@@ -1,8 +1,10 @@
 #ifndef __ARCH_I386_ATOMIC__
 #define __ARCH_I386_ATOMIC__
 
 #include <linux/config.h>
+#include <linux/compiler.h>
+#include <asm/processor.h>
 
 /*
  * Atomic operations that C can't guarantee us.  Useful for
  * resource counting etc..
@@ -175,8 +177,48 @@
 		:"ir" (i), "m" (v->counter) : "memory");
 	return c;
 }
 
+/**
+ * atomic_add_return - add and return
+ * @v: pointer of type atomic_t
+ * @i: integer value to add
+ *
+ * Atomically adds @i to @v and returns @i + @v
+ */
+static __inline__ int atomic_add_return(int i, atomic_t *v)
+{
+	int __i;
+#ifdef CONFIG_M386
+	if(unlikely(boot_cpu_data.x86==3))
+		goto no_xadd;
+#endif
+	/* Modern 486+ processor */
+	__i = i;
+	__asm__ __volatile__(
+		LOCK "xaddl %0, %1;"
+		:"=r"(i)
+		:"m"(v->counter), "0"(i));
+	return i + __i;
+
+#ifdef CONFIG_M386
+no_xadd: /* Legacy 386 processor */
+	local_irq_disable();
+	__i = atomic_read(v);
+	atomic_set(v, i + __i);
+	local_irq_enable();
+	return i + __i;
+#endif
+}
+
+static __inline__ int atomic_sub_return(int i, atomic_t *v)
+{
+	return atomic_add_return(-i,v);
+}
+
+#define atomic_inc_return(v)  (atomic_add_return(1,v))
+#define atomic_dec_return(v)  (atomic_sub_return(1,v))
+
 /* These are x86-specific, used by some header files */
 #define atomic_clear_mask(mask, addr) \
 __asm__ __volatile__(LOCK "andl %0,%1" \
 : : "r" (~(mask)),"m" (*addr) : "memory")

[PATCH] atomic_inc_return() for x86_64[2/5] (Re: atomic_inc_return)

[Kaigai Kohei]

[2/5] atomic_inc_return-linux-2.6.9-rc1.x86_64.patch
  This patch implements atomic_inc_return() and so on for x86_64.
  It is same as I posted to LKML and Andi Kleen at '04/09/01.

Signed-off-by: KaiGai, Kohei <kaigai@ak.jp.nec.com>
--------
Kai Gai <kaigai@ak.jp.nec.com>


diff -rNU4 linux-2.6.9-rc1/include/asm-x86_64/atomic.h linux-2.6.9-rc1.atomic_inc_return/include/asm-x86_64/atomic.h
--- linux-2.6.9-rc1/include/asm-x86_64/atomic.h	2004-08-24 16:03:38.000000000 +0900
+++ linux-2.6.9-rc1.atomic_inc_return/include/asm-x86_64/atomic.h	2004-09-10 10:15:18.000000000 +0900
@@ -177,8 +177,33 @@
 		:"ir" (i), "m" (v->counter) : "memory");
 	return c;
 }
 
+/**
+ * atomic_add_return - add and return
+ * @v: pointer of type atomic_t
+ * @i: integer value to add
+ *
+ * Atomically adds @i to @v and returns @i + @v
+ */
+static __inline__ int atomic_add_return(int i, atomic_t *v)
+{
+	int __i = i;
+	__asm__ __volatile__(
+		LOCK "xaddl %0, %1;"
+		:"=r"(i)
+		:"m"(v->counter), "0"(i));
+	return i + __i;
+}
+
+static __inline__ int atomic_sub_return(int i, atomic_t *v)
+{
+	return atomic_add_return(-i,v);
+}
+
+#define atomic_inc_return(v)  (atomic_add_return(1,v))
+#define atomic_dec_return(v)  (atomic_sub_return(1,v))
+
 /* These are x86-specific, used by some header files */
 #define atomic_clear_mask(mask, addr) \
 __asm__ __volatile__(LOCK "andl %0,%1" \
 : : "r" (~(mask)),"m" (*addr) : "memory")

[PATCH] atomic_inc_return() for arm[3/5] (Re: atomic_inc_return)

[Kaigai Kohei]

[3/5] atomic_inc_return-linux-2.6.9-rc1.arm.patch
  This patch declares atomic_inc_return() as the alias of atomic_add_return()
  and atomic_dec_return() as an alias of atomic_dec_return().
  This patch has not been tested, since we don't have ARM machine.
  I want to let this reviewed by ARM specialists.

Signed-off-by: KaiGai, Kohei <kaigai@ak.jp.nec.com>
--------
Kai Gai <kaigai@ak.jp.nec.com>


diff -rNU4 linux-2.6.9-rc1/include/asm-arm/atomic.h linux-2.6.9-rc1.atomic_inc_return/include/asm-arm/atomic.h
--- linux-2.6.9-rc1/include/asm-arm/atomic.h	2004-08-24 16:01:55.000000000 +0900
+++ linux-2.6.9-rc1.atomic_inc_return/include/asm-arm/atomic.h	2004-09-10 10:15:18.000000000 +0900
@@ -194,8 +194,10 @@
 #define atomic_dec(v)		atomic_sub(1, v)
 
 #define atomic_inc_and_test(v)	(atomic_add_return(1, v) == 0)
 #define atomic_dec_and_test(v)	(atomic_sub_return(1, v) == 0)
+#define atomic_inc_return(v)    (atomic_add_return(1, v))
+#define atomic_dec_return(v)    (atomic_sub_return(1, v))
 
 #define atomic_add_negative(i,v) (atomic_add_return(i, v) < 0)
 
 /* Atomic operations are already serializing on ARM */

[PATCH] atomic_inc_return() for arm26[1/5] (Re: atomic_inc_return)

[Kaigai Kohei]

[4/5] atomic_inc_return-linux-2.6.9-rc1.arm26.patch
  This patch implements atomic_inc_return() and so on for ARM26.
  Because Hugh says that SMP is not supported in arm26, it is implemented
  by normal operations between local_irq_save() and local_irq_restore()
  like another atomic operations.
  This patch has not been tested, since we don't have ARM26 machine.
  I want to let this reviewed by ARM26 specialists.

Signed-off-by: KaiGai, Kohei <kaigai@ak.jp.nec.com>
--------
Kai Gai <kaigai@ak.jp.nec.com>


diff -rNU4 linux-2.6.9-rc1/include/asm-arm26/atomic.h linux-2.6.9-rc1.atomic_inc_return/include/asm-arm26/atomic.h
--- linux-2.6.9-rc1/include/asm-arm26/atomic.h	2004-08-24 16:02:32.000000000 +0900
+++ linux-2.6.9-rc1.atomic_inc_return/include/asm-arm26/atomic.h	2004-09-10 10:20:29.000000000 +0900
@@ -104,8 +104,29 @@
 	*addr &= ~mask;
 	local_irq_restore(flags);
 }
 
+static inline int atomic_add_return(int i, volatile atomic_t *v)
+{
+	unsigned long flags;
+	int val;
+
+	local_irq_save(flags);
+	val = v->counter + i;
+	v->counter = val;
+	local_irq_restore(flags);
+
+	return val;
+}
+
+static inline int atomic_sub_return(int i, volatile atomic_t *v)
+{
+	return atomic_add_return(-i, v);
+}
+
+#define atomic_inc_return(v)  (atomic_add_return(1,v))
+#define atomic_dec_return(v)  (atomic_sub_return(1,v))
+
 /* Atomic operations are already serializing on ARM */
 #define smp_mb__before_atomic_dec()	barrier()
 #define smp_mb__after_atomic_dec()	barrier()
 #define smp_mb__before_atomic_inc()	barrier()

[PATCH] atomic_inc_return() for sparc64[5/5] (Re: atomic_inc_return)

[Kaigai Kohei]

[5/5] atomic_inc_return-linux-2.6.9-rc1.sparc64.patch
  This patch declares atomic_add_return() as an alias of __atomic_add().
  atomic64_add_return(),atomic_sub_return() and atomic64_sub_return() are same.
  This patch has not been tested, since we don't have SPARC64 machine.  
  I want to let this reviewed by SPARC64 specialists.

Signed-off-by: KaiGai, Kohei <kaigai@ak.jp.nec.com>
--------
Kai Gai <kaigai@ak.jp.nec.com>


diff -rNU4 linux-2.6.9-rc1/include/asm-sparc64/atomic.h linux-2.6.9-rc1.atomic_inc_return/include/asm-sparc64/atomic.h
--- linux-2.6.9-rc1/include/asm-sparc64/atomic.h	2004-08-24 16:03:32.000000000 +0900
+++ linux-2.6.9-rc1.atomic_inc_return/include/asm-sparc64/atomic.h	2004-09-10 10:13:25.000000000 +0900
@@ -39,8 +39,14 @@
 
 #define atomic_inc_return(v) __atomic_add(1, v)
 #define atomic64_inc_return(v) __atomic64_add(1, v)
 
+#define atomic_sub_return(i, v) __atomic_sub(i, v)
+#define atomic64_sub_return(i, v) __atomic64_sub(i, v)
+
+#define atomic_add_return(i, v) __atomic_add(i, v)
+#define atomic64_add_return(i, v) __atomic64_add(i, v)
+
 /*
  * atomic_inc_and_test - increment and test
  * @v: pointer of type atomic_t
  *

PATCH] atomic_inc_return() [0/5] (Re: atomic_inc_return)

[Kaigai Kohei]

The first mail to LKML was returned to me because Triple-X was in subject.
I tried to send this one again.
---------------------------

Hello, Hugh Dickins

> KaiGai-San,
> 
> I believe you have a patch adding those to i386 (including CONFIG_M386
> runtime check lest it's an actual i386 which cannot do "xadd") and x86_64.
> I'd be glad to see that go into the tree, would you be ready to submit it
> to Andrew or Linus based on the current 2.6 BK tree?

Indeed, I hope to do this.
atomic_inc_return() is necessary for the 'SELinux performance improvement
by RCU' patch.

See, http://lkml.org/lkml/2004/8/30/63
  [PATCH]SELinux performance improvement by RCU (Re: RCU issue with SELinux)

These fundamental functions should be managed in up-stream.

> I think arm was missing the inc and dec, but has recently gained them.
> arm26 doesn't have any of the four, but it's not SMP, and just a matter
> of following the other examples in its atomic.h to add them.  sparc64
> is missing the add and sub (which neither of us particularly need),
> I think just because nobody was using them: easily added - I think
> it'd be a good idea for all architectures to have the set of four.

I made patches for i386, x86_64, arm, arm26 and sparc64.
These patches apply to both linux-2.6.9-rc1 and 2.6.9-rc1-mm4.

[1/5] atomic_inc_return-linux-2.6.9-rc1.i386.patch
  This patch implements atomic_inc_return() and so on for i386,
  and includes runtime check whether CPU is legacy 386.
  It is same as I posted to LKML and Andi Kleen at '04/09/01.

[2/5] atomic_inc_return-linux-2.6.9-rc1.x86_64.patch
  This patch implements atomic_inc_return() and so on for x86_64.
  It is same as I posted to LKML and Andi Kleen at '04/09/01.

[3/5] atomic_inc_return-linux-2.6.9-rc1.arm.patch
  This patch declares atomic_inc_return() as the alias of atomic_add_return()
  and atomic_dec_return() as an alias of atomic_dec_return().
  This patch has not been tested, since we don't have ARM machine.
  I want to let this reviewed by ARM specialists.

[4/5] atomic_inc_return-linux-2.6.9-rc1.arm26.patch
  This patch implements atomic_inc_return() and so on for ARM26.
  Because Hugh says that SMP is not supported in arm26, it is implemented
  by normal operations between local_irq_save() and local_irq_restore()
  like another atomic operations.
  This patch has not been tested, since we don't have ARM26 machine.
  I want to let this reviewed by ARM26 specialists.

[5/5] atomic_inc_return-linux-2.6.9-rc1.sparc64.patch
  This patch declares atomic_add_return() as an alias of __atomic_add().
  atomic64_add_return(),atomic_sub_return() and atomic64_sub_return() are same.
  This patch has not been tested, since we don't have SPARC64 machine.  
  I want to let this reviewed by SPARC64 specialists.

--------
Kai Gai <kaigai@ak.jp.nec.com>


> Andrew,
> 
> Sorry, I think I must ask you to back my lighten-mmlist_lock.patch
> out of -mm for the moment, and I'll resubmit a little later on.
> 
> Reason being, though nobody is at all likely to hit the race,
> I've put a pathetic piece of self-delusion in try_to_unuse:
> if (!atomic_read(&mm->mm_users))
> continue;
>   atomic_inc(&mm->mm_users);
> 
> I've tried several ways of fixing it (including reworking that dance
> using marker mms instead of raised counts), but got bored or given up
> in disgust over most of them.  Much the nicest fix would be:
> if (atomic_inc_return(&mm->mm_users) == 1) {
> atomic_dec(&mm->mm_users);
> continue;
> }
> 
> (Since, if mm_users was 0, try_to_unuse is the only one which could
> be incrementing it; and though it's possible to do two swapoffs at
> once, we here have the mmlist_lock guarding against another.)
> 
> But that suffers from the drawback that not all architectures currently
> support atomic_inc_return (nor do all support cmpxchg, which could have
> been used instead), and its friends atomic_add_return, atomic_sub_return,
> atomic_dec_return.  Though most do: wouldn't it be nice if they all did?
> 
> KaiGai-San,
> 
> I believe you have a patch adding those to i386 (including CONFIG_M386
> runtime check lest it's an actual i386 which cannot do "xadd") and x86_64.
> I'd be glad to see that go into the tree, would you be ready to submit it
> to Andrew or Linus based on the current 2.6 BK tree?
> 
> I think arm was missing the inc and dec, but has recently gained them.
> arm26 doesn't have any of the four, but it's not SMP, and just a matter
> of following the other examples in its atomic.h to add them.  sparc64
> is missing the add and sub (which neither of us particularly need),
> I think just because nobody was using them: easily added - I think
> it'd be a good idea for all architectures to have the set of four.
> 
> Hirokazu-San,
> 
> That leaves your m32r architecture without them: are those functions
> which you could easily add to the m32r atomic.h, or would there be a
> problem with them?  I'd hate to break your newly-arrived architecture!
> 
> Thanks,
> Hugh
> 

Re: [PATCH] atomic_inc_return() for sparc64[5/5] (Re: atomic_inc_return)

[David S. Miller]

On Fri, 10 Sep 2004 12:32:06 +0900 (JST)
kaigai@ak.jp.nec.com (Kaigai Kohei) wrote:

> 
> [5/5] atomic_inc_return-linux-2.6.9-rc1.sparc64.patch
>   This patch declares atomic_add_return() as an alias of __atomic_add().
>   atomic64_add_return(),atomic_sub_return() and atomic64_sub_return() are same.
>   This patch has not been tested, since we don't have SPARC64 machine.  
>   I want to let this reviewed by SPARC64 specialists.
> 
> Signed-off-by: KaiGai, Kohei <kaigai@ak.jp.nec.com>

This looks fine to me.

Re: [PATCH] atomic_inc_return() for i386[1/5] (Re: atomic_inc_return)

[Chris Wedgwood]

On Fri, Sep 10, 2004 at 12:26:54PM +0900, Kaigai Kohei wrote:

> +static __inline__ int atomic_add_return(int i, atomic_t *v)
> +{
> +	int __i;
> +#ifdef CONFIG_M386
> +	if(unlikely(boot_cpu_data.x86==3))
> +		goto no_xadd;
> +#endif

i didn't check what code is generated, but isn't that expensive?  i
guess most people building i386 kernels want maximum compatability so
it probably doesn't matter...

Re: PATCH] atomic_inc_return() [0/5] (Re: atomic_inc_return)

[Hugh Dickins]

On Fri, 10 Sep 2004, Kaigai Kohei wrote:
> > 
> > I believe you have a patch adding those to i386 (including CONFIG_M386
> > runtime check lest it's an actual i386 which cannot do "xadd") and x86_64.
> > I'd be glad to see that go into the tree, would you be ready to submit it
> > to Andrew or Linus based on the current 2.6 BK tree?
> 
> Indeed, I hope to do this.
> atomic_inc_return() is necessary for the 'SELinux performance improvement
> by RCU' patch.

Thanks a lot, the patches 1-5 you've posted look good to me (aside from
some spaces instead of tab in the asm-arm 3/5), and should save me from
my silly race.

If we'd had these earlier, we could have avoiding changing page->count
and page->mapcount over to start from -1 (though I dare say they may
be slightly more efficient as they now are, than if we converted them
back).  Should save making such conversions in future, anyway.

> > I think arm was missing the inc and dec, but has recently gained them.

I was wrong when I said that: asm-arm/atomic.h has recently been reworked,
but does still needs your additions: sorry for the confusion.

Thanks,
Hugh

Re: [PATCH] atomic_inc_return() for i386[1/5] (Re: atomic_inc_return)

[Andrew Morton]

kaigai@ak.jp.nec.com (Kaigai Kohei) wrote:
>
> 
> [1/5] atomic_inc_return-linux-2.6.9-rc1.i386.patch
>   This patch implements atomic_inc_return() and so on for i386,
>   and includes runtime check whether CPU is legacy 386.
>   It is same as I posted to LKML and Andi Kleen at '04/09/01.
> 

Can we not use the `alternative instruction' stuff to eliminate the runtime
test?


> 
> diff -rNU4 linux-2.6.9-rc1/include/asm-i386/atomic.h linux-2.6.9-rc1.atomic_inc_return/include/asm-i386/atomic.h
> --- linux-2.6.9-rc1/include/asm-i386/atomic.h	2004-08-24 16:02:24.000000000 +0900
> +++ linux-2.6.9-rc1.atomic_inc_return/include/asm-i386/atomic.h	2004-09-10 10:15:18.000000000 +0900
> @@ -1,8 +1,10 @@
>  #ifndef __ARCH_I386_ATOMIC__
>  #define __ARCH_I386_ATOMIC__
>  
>  #include <linux/config.h>
> +#include <linux/compiler.h>
> +#include <asm/processor.h>
>  
>  /*
>   * Atomic operations that C can't guarantee us.  Useful for
>   * resource counting etc..
> @@ -175,8 +177,48 @@
>  		:"ir" (i), "m" (v->counter) : "memory");
>  	return c;
>  }
>  
> +/**
> + * atomic_add_return - add and return
> + * @v: pointer of type atomic_t
> + * @i: integer value to add
> + *
> + * Atomically adds @i to @v and returns @i + @v
> + */
> +static __inline__ int atomic_add_return(int i, atomic_t *v)
> +{
> +	int __i;
> +#ifdef CONFIG_M386
> +	if(unlikely(boot_cpu_data.x86==3))
> +		goto no_xadd;
> +#endif
> +	/* Modern 486+ processor */
> +	__i = i;
> +	__asm__ __volatile__(
> +		LOCK "xaddl %0, %1;"
> +		:"=r"(i)
> +		:"m"(v->counter), "0"(i));
> +	return i + __i;
> +
> +#ifdef CONFIG_M386
> +no_xadd: /* Legacy 386 processor */
> +	local_irq_disable();
> +	__i = atomic_read(v);
> +	atomic_set(v, i + __i);
> +	local_irq_enable();
> +	return i + __i;
> +#endif
> +}
> +
> +static __inline__ int atomic_sub_return(int i, atomic_t *v)
> +{
> +	return atomic_add_return(-i,v);
> +}
> +
> +#define atomic_inc_return(v)  (atomic_add_return(1,v))
> +#define atomic_dec_return(v)  (atomic_sub_return(1,v))
> +
>  /* These are x86-specific, used by some header files */
>  #define atomic_clear_mask(mask, addr) \
>  __asm__ __volatile__(LOCK "andl %0,%1" \
>  : : "r" (~(mask)),"m" (*addr) : "memory")

Re: [PATCH] atomic_inc_return() for i386[1/5] (Re: atomic_inc_return)

[Andi Kleen]

On Sat, Sep 11, 2004 at 04:05:32PM -0700, Andrew Morton wrote:
> kaigai@ak.jp.nec.com (Kaigai Kohei) wrote:
> >
> > 
> > [1/5] atomic_inc_return-linux-2.6.9-rc1.i386.patch
> >   This patch implements atomic_inc_return() and so on for i386,
> >   and includes runtime check whether CPU is legacy 386.
> >   It is same as I posted to LKML and Andi Kleen at '04/09/01.
> > 
> 
> Can we not use the `alternative instruction' stuff to eliminate the runtime
> test?

Yes, we could. I suggested this to Kaigai-san earlier, but
he decided that it was too complicated because he would have needed
to add an additional alternative() macro with enough parameters.

Given that atomic instructions are quite costly anyways and the jump
should be very predictable he's probably right that it wouldn't 
be worth the effort. 

-Andi

Re: [PATCH] atomic_inc_return() for i386[1/5] (Re: atomic_inc_return)

[Andrew Morton]

Andi Kleen <ak@muc.de> wrote:
>
> On Sat, Sep 11, 2004 at 04:05:32PM -0700, Andrew Morton wrote:
> > kaigai@ak.jp.nec.com (Kaigai Kohei) wrote:
> > >
> > > 
> > > [1/5] atomic_inc_return-linux-2.6.9-rc1.i386.patch
> > >   This patch implements atomic_inc_return() and so on for i386,
> > >   and includes runtime check whether CPU is legacy 386.
> > >   It is same as I posted to LKML and Andi Kleen at '04/09/01.
> > > 
> > 
> > Can we not use the `alternative instruction' stuff to eliminate the runtime
> > test?
> 
> Yes, we could. I suggested this to Kaigai-san earlier, but
> he decided that it was too complicated because he would have needed
> to add an additional alternative() macro with enough parameters.
> 
> Given that atomic instructions are quite costly anyways and the jump
> should be very predictable he's probably right that it wouldn't 
> be worth the effort. 
> 

Hm.  Well if these things only have a few callsites then OK.  But if we go
and do something like implementing atomic_inc() or up_read() or whatever
with atomic_add_return() then we'd need to do something from a codesize
POV.