[PATCH] atomic: add atomic_inc_not_zero_hint()

[PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Andrew

atomic_inc_not_zero() / atomic_add_unless() ... are spreaded in many
arch/xxx/include/asm/atomic.h, but they are generic.

Apparently there is no centralization of some common atomic features...

What do you think adding a new file so that we can move common
definitions in it ?

Thanks

[PATCH] atomic: add atomic_inc_not_zero_hint()

Followup of perf tools session in Netfilter WorkShop 2010

In network stack we make high usage of atomic_inc_not_zero() in contexts
we know the probable value of atomic before increment (2 for udp sockets
for example)

Using a special version of atomic_inc_not_zero() giving this hint can
help processor to use less bus transactions.

On x86 (MESI protocol) for example, this avoids entering Shared state,
because "lock cmpxchg" issues an RFO (Read For Ownership)

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Christoph Lameter <cl@linux-foundation.org>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Andi Kleen <andi@firstfloor.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: David Miller <davem@davemloft.net>
Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Cc: Nick Piggin <npiggin@kernel.dk>
---
 include/linux/atomic.h |   29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/include/linux/atomic.h b/include/linux/atomic.h
new file mode 100644
index 0000000..c04327a
--- /dev/null
+++ b/include/linux/atomic.h
@@ -0,0 +1,29 @@
+#ifndef _LINUX_ATOMIC_H
+#define _LINUX_ATOMIC_H
+#include <asm/atomic.h>
+
+/**
+ * atomic_inc_not_zero_hint - increment if not null
+ * @v: pointer of type atomic_t
+ * @hint: probable value of the atomic before the increment
+ *
+ * This version of atomic_inc_not_zero() gives a hint of probable
+ * value of the atomic. This helps processor to not read the memory
+ * before doing the atomic read/modify/write cycle, lowering
+ * number of bus transactions on some arches.
+ * Note: hint MUST not be 0 !
+ */
+static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
+{
+	int val, c = hint;
+
+ 	do {
+		val = atomic_cmpxchg(v, c, c + 1);
+		if (val == c)
+			return 1;
+		c = val;
+	} while (c);
+
+	return 0;
+}
+#endif /* _LINUX_ATOMIC_H */

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Andrew Morton]

On Fri, 05 Nov 2010 17:53:00 +0100
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> Andrew
> 
> atomic_inc_not_zero() / atomic_add_unless() ... are spreaded in many
> arch/xxx/include/asm/atomic.h, but they are generic.
> 
> Apparently there is no centralization of some common atomic features...
> 
> What do you think adding a new file so that we can move common
> definitions in it ?
> 
> Thanks
> 
> [PATCH] atomic: add atomic_inc_not_zero_hint()
> 
> Followup of perf tools session in Netfilter WorkShop 2010
> 
> In network stack we make high usage of atomic_inc_not_zero() in contexts
> we know the probable value of atomic before increment (2 for udp sockets
> for example)
> 
> Using a special version of atomic_inc_not_zero() giving this hint can
> help processor to use less bus transactions.
> 
> On x86 (MESI protocol) for example, this avoids entering Shared state,
> because "lock cmpxchg" issues an RFO (Read For Ownership)

It totally makes sense to add include/linu/atomic.h for common things. 
Perhaps there's already code in arch/*/include/asm/atomic.h which
should be hoisted up there.  But that can't reliably be done until a
million files have had their #includes switched :(

> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
> Cc: Christoph Lameter <cl@linux-foundation.org>
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Andi Kleen <andi@firstfloor.org>
> Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
> Cc: David Miller <davem@davemloft.net>
> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> Cc: Nick Piggin <npiggin@kernel.dk>
> ---
>  include/linux/atomic.h |   29 +++++++++++++++++++++++++++++
>  1 file changed, 29 insertions(+)
> 
> diff --git a/include/linux/atomic.h b/include/linux/atomic.h
> new file mode 100644
> index 0000000..c04327a
> --- /dev/null
> +++ b/include/linux/atomic.h
> @@ -0,0 +1,29 @@
> +#ifndef _LINUX_ATOMIC_H
> +#define _LINUX_ATOMIC_H
> +#include <asm/atomic.h>
> +
> +/**
> + * atomic_inc_not_zero_hint - increment if not null
> + * @v: pointer of type atomic_t
> + * @hint: probable value of the atomic before the increment
> + *
> + * This version of atomic_inc_not_zero() gives a hint of probable
> + * value of the atomic. This helps processor to not read the memory
> + * before doing the atomic read/modify/write cycle, lowering
> + * number of bus transactions on some arches.
> + * Note: hint MUST not be 0 !
> + */

It's quite unobvious *why* `hint' cannot be zero.  Can you please add
the reasoning to the comment?  Also, the local `hint' should be
referred to as "@hint" in a kerneldoc comment.

> +static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
> +{
> +	int val, c = hint;
> +
> + 	do {
> +		val = atomic_cmpxchg(v, c, c + 1);
> +		if (val == c)
> +			return 1;
> +		c = val;
> +	} while (c);
> +
> +	return 0;
> +}

Should/could this have implemented a more general
atomic_add_not_zero_hint() and made atomic_inc_not_zero_hint() a
wrapper around that?

Also, it might make sense to add "#ifndef atomic_inc_not_zero_hint"
wrappers around this function so that the arch can implement an
overriding custom version.  And that becomes a general rule as more
functions are added to include/linux/atomic.h.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le vendredi 05 novembre 2010 à 10:20 -0700, Andrew Morton a écrit :

> It totally makes sense to add include/linu/atomic.h for common things. 
> Perhaps there's already code in arch/*/include/asm/atomic.h which
> should be hoisted up there.  But that can't reliably be done until a
> million files have had their #includes switched :(
> 

Maybe including <linux/atomic.h> only from the end of various

arch/*/include/asm/atomic.h  ?

In this case, I remove the include <asm/atomic.h> from linux/atomic.h

> It's quite unobvious *why* `hint' cannot be zero.  Can you please add
> the reasoning to the comment?  Also, the local `hint' should be
> referred to as "@hint" in a kerneldoc comment.

Well ;)

We want to increment the counter if its not zero.
Typically used for refcounts, of RCU protected structures.

Giving a zero hint would be curious dont you think ?

I see no usage for this, and using atomic_inc_not_zero() in this case is
the only choice, since we dont ever want to cmpxchg(v, 0, 1) (or risk
double free and crazy things)

Hmm... maybe I can add a test (compiler should optimize it anyway, since
all usages I can foresee will use a constant hint)

> 
> > +static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
> > +{
> > +	int val, c = hint;
> > +
> > + 	do {
> > +		val = atomic_cmpxchg(v, c, c + 1);
> > +		if (val == c)
> > +			return 1;
> > +		c = val;
> > +	} while (c);
> > +
> > +	return 0;
> > +}
> 
> Should/could this have implemented a more general
> atomic_add_not_zero_hint() and made atomic_inc_not_zero_hint() a
> wrapper around that?

Well, I see no practical use for this, but yes, this could be done.

As atomic_add_not_zero() doesnt exist, I am not sure we need an
atomic_add_not_zero_hint() yet ?

> 
> Also, it might make sense to add "#ifndef atomic_inc_not_zero_hint"
> wrappers around this function so that the arch can implement an
> overriding custom version.  And that becomes a general rule as more
> functions are added to include/linux/atomic.h.

Ah yes, thats right !

Thanks !

[PATCH v2] atomic: add atomic_inc_not_zero_hint()

Followup of perf tools session in Netfilter WorkShop 2010

In network stack we make high usage of atomic_inc_not_zero() in contexts
we know the probable value of atomic before increment (2 for udp sockets
for example)

Using a special version of atomic_inc_not_zero() giving this hint can
help processor to use less bus transactions.

On x86 (MESI protocol) for example, this avoids entering Shared state,
because "lock cmpxchg" issues an RFO (Read For Ownership)

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Christoph Lameter <cl@linux-foundation.org>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Andi Kleen <andi@firstfloor.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: David Miller <davem@davemloft.net>
Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Cc: Nick Piggin <npiggin@kernel.dk>
---
V2: add #ifndef atomic_inc_not_zero_hint
    kerneldoc changes
    test that hint is not null
    Meant to be included at end of arch/*/asm/atomic.h files

 include/linux/atomic.h |   36 ++++++++++++++++++++++++++++++++++++
 1 files changed, 36 insertions(+)

diff --git a/include/linux/atomic.h b/include/linux/atomic.h
new file mode 100644
index 0000000..0897bdd
--- /dev/null
+++ b/include/linux/atomic.h
@@ -0,0 +1,36 @@
+#ifndef _LINUX_ATOMIC_H
+#define _LINUX_ATOMIC_H
+
+/**
+ * atomic_inc_not_zero_hint - increment if not null
+ * @v: pointer of type atomic_t
+ * @hint: probable value of the atomic before the increment
+ *
+ * This version of atomic_inc_not_zero() gives a hint of probable
+ * value of the atomic. This helps processor to not read memory
+ * before doing the atomic read/modify/write cycle, lowering
+ * number of bus transactions on some arches.
+ * Note: @hint MUST not be 0, or increment is not done.
+ * Returns: 0 if increment was not done, 1 otherwise.
+ */
+#ifndef atomic_inc_not_zero_hint
+static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
+{
+	int val, c = hint;
+
+	/* sanity test, should be removed by compiler if hint is a constant */
+	if (!hint)
+		return 0;
+
+ 	do {
+		val = atomic_cmpxchg(v, c, c + 1);
+		if (val == c)
+			return 1;
+		c = val;
+	} while (c);
+
+	return 0;
+}
+#endif
+
+#endif /* _LINUX_ATOMIC_H */

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Andrew Morton]

On Fri, 05 Nov 2010 19:00:46 +0100
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> Le vendredi 05 novembre 2010 __ 10:20 -0700, Andrew Morton a __crit :
> 
> > It totally makes sense to add include/linu/atomic.h for common things. 
> > Perhaps there's already code in arch/*/include/asm/atomic.h which
> > should be hoisted up there.  But that can't reliably be done until a
> > million files have had their #includes switched :(
> > 
> 
> Maybe including <linux/atomic.h> only from the end of various
> 
> arch/*/include/asm/atomic.h  ?

heh, I guess that would work.  It breaks the standard way of doing
these things (I think?) so let's not go there unless we have a need?

> In this case, I remove the include <asm/atomic.h> from linux/atomic.h

Oh.  Why?  I thought it was better the previous, standard way: thou
shalt henceforth include liunx/atomic.h, not asm/atomic.h.  And the
presence of linux/atomic.h will in fact trigger the checkpatch warning
telling people to use that when they try to use asm/atomic.h.

> > > +static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
> > > +{
> > > +	int val, c = hint;
> > > +
> > > + 	do {
> > > +		val = atomic_cmpxchg(v, c, c + 1);
> > > +		if (val == c)
> > > +			return 1;
> > > +		c = val;
> > > +	} while (c);
> > > +
> > > +	return 0;
> > > +}
> > 
> > Should/could this have implemented a more general
> > atomic_add_not_zero_hint() and made atomic_inc_not_zero_hint() a
> > wrapper around that?
> 
> Well, I see no practical use for this, but yes, this could be done.
> 
> As atomic_add_not_zero() doesnt exist, I am not sure we need an
> atomic_add_not_zero_hint() yet ?

hm, OK.  I was just checking ;)

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le vendredi 05 novembre 2010 à 11:08 -0700, Andrew Morton a écrit :
> On Fri, 05 Nov 2010 19:00:46 +0100
> Eric Dumazet <eric.dumazet@gmail.com> wrote:
> 
> > Le vendredi 05 novembre 2010 __ 10:20 -0700, Andrew Morton a __crit :
> > 
> > > It totally makes sense to add include/linu/atomic.h for common things. 
> > > Perhaps there's already code in arch/*/include/asm/atomic.h which
> > > should be hoisted up there.  But that can't reliably be done until a
> > > million files have had their #includes switched :(
> > > 
> > 
> > Maybe including <linux/atomic.h> only from the end of various
> > 
> > arch/*/include/asm/atomic.h  ?
> 
> heh, I guess that would work.  It breaks the standard way of doing
> these things (I think?) so let's not go there unless we have a need?
> 
> > In this case, I remove the include <asm/atomic.h> from linux/atomic.h
> 
> Oh.  Why?  I thought it was better the previous, standard way: thou
> shalt henceforth include liunx/atomic.h, not asm/atomic.h.  And the
> presence of linux/atomic.h will in fact trigger the checkpatch warning
> telling people to use that when they try to use asm/atomic.h.

Hmm, if we want to move the common stuff from
arch/*/include/asm/atomic.h to this new file (include/linux/atomic.h),
then we would have to change hundred of 

#include <asm/atomic.h> 

to

#include <linux/atomic.h> 

This seems a big task to me ?

Or just make a whole tree replace ?

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Andrew Morton]

On Fri, 05 Nov 2010 19:20:24 +0100
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> Le vendredi 05 novembre 2010 __ 11:08 -0700, Andrew Morton a __crit :
> > On Fri, 05 Nov 2010 19:00:46 +0100
> > Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > 
> > > Le vendredi 05 novembre 2010 __ 10:20 -0700, Andrew Morton a __crit :
> > > 
> > > > It totally makes sense to add include/linu/atomic.h for common things. 
> > > > Perhaps there's already code in arch/*/include/asm/atomic.h which
> > > > should be hoisted up there.  But that can't reliably be done until a
> > > > million files have had their #includes switched :(
> > > > 
> > > 
> > > Maybe including <linux/atomic.h> only from the end of various
> > > 
> > > arch/*/include/asm/atomic.h  ?
> > 
> > heh, I guess that would work.  It breaks the standard way of doing
> > these things (I think?) so let's not go there unless we have a need?
> > 
> > > In this case, I remove the include <asm/atomic.h> from linux/atomic.h
> > 
> > Oh.  Why?  I thought it was better the previous, standard way: thou
> > shalt henceforth include liunx/atomic.h, not asm/atomic.h.  And the
> > presence of linux/atomic.h will in fact trigger the checkpatch warning
> > telling people to use that when they try to use asm/atomic.h.
> 
> Hmm, if we want to move the common stuff from
> arch/*/include/asm/atomic.h to this new file (include/linux/atomic.h),
> then we would have to change hundred of 
> 
> #include <asm/atomic.h> 
> 
> to
> 
> #include <linux/atomic.h> 
> 
> This seems a big task to me ?
> 
> Or just make a whole tree replace ?
> 

But we haven't established that there _is_ duplicated code which needs
that treatment.

Scanning arch/x86/include/asm/atomic.h, perhaps ATOMIC_INIT() is a
candidate.  But I'm not sure that it _should_ be hoisted up - if every
architecture happens to do it the same way then that's just a fluke.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Paul E. McKenney]

On Fri, Nov 05, 2010 at 07:00:46PM +0100, Eric Dumazet wrote:
> Le vendredi 05 novembre 2010 à 10:20 -0700, Andrew Morton a écrit :
> 
> > It totally makes sense to add include/linu/atomic.h for common things. 
> > Perhaps there's already code in arch/*/include/asm/atomic.h which
> > should be hoisted up there.  But that can't reliably be done until a
> > million files have had their #includes switched :(
> > 
> 
> Maybe including <linux/atomic.h> only from the end of various
> 
> arch/*/include/asm/atomic.h  ?
> 
> In this case, I remove the include <asm/atomic.h> from linux/atomic.h
> 
> > It's quite unobvious *why* `hint' cannot be zero.  Can you please add
> > the reasoning to the comment?  Also, the local `hint' should be
> > referred to as "@hint" in a kerneldoc comment.
> 
> Well ;)
> 
> We want to increment the counter if its not zero.
> Typically used for refcounts, of RCU protected structures.
> 
> Giving a zero hint would be curious dont you think ?
> 
> I see no usage for this, and using atomic_inc_not_zero() in this case is
> the only choice, since we dont ever want to cmpxchg(v, 0, 1) (or risk
> double free and crazy things)
> 
> Hmm... maybe I can add a test (compiler should optimize it anyway, since
> all usages I can foresee will use a constant hint)
> 
> > 
> > > +static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
> > > +{
> > > +	int val, c = hint;
> > > +
> > > + 	do {
> > > +		val = atomic_cmpxchg(v, c, c + 1);
> > > +		if (val == c)
> > > +			return 1;
> > > +		c = val;
> > > +	} while (c);
> > > +
> > > +	return 0;
> > > +}
> > 
> > Should/could this have implemented a more general
> > atomic_add_not_zero_hint() and made atomic_inc_not_zero_hint() a
> > wrapper around that?
> 
> Well, I see no practical use for this, but yes, this could be done.
> 
> As atomic_add_not_zero() doesnt exist, I am not sure we need an
> atomic_add_not_zero_hint() yet ?
> 
> > 
> > Also, it might make sense to add "#ifndef atomic_inc_not_zero_hint"
> > wrappers around this function so that the arch can implement an
> > overriding custom version.  And that becomes a general rule as more
> > functions are added to include/linux/atomic.h.
> 
> Ah yes, thats right !
> 
> Thanks !
> 
> [PATCH v2] atomic: add atomic_inc_not_zero_hint()
> 
> Followup of perf tools session in Netfilter WorkShop 2010
> 
> In network stack we make high usage of atomic_inc_not_zero() in contexts
> we know the probable value of atomic before increment (2 for udp sockets
> for example)
> 
> Using a special version of atomic_inc_not_zero() giving this hint can
> help processor to use less bus transactions.
> 
> On x86 (MESI protocol) for example, this avoids entering Shared state,
> because "lock cmpxchg" issues an RFO (Read For Ownership)
> 
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
> Cc: Christoph Lameter <cl@linux-foundation.org>
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Andi Kleen <andi@firstfloor.org>
> Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
> Cc: David Miller <davem@davemloft.net>
> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> Cc: Nick Piggin <npiggin@kernel.dk>
> ---
> V2: add #ifndef atomic_inc_not_zero_hint
>     kerneldoc changes
>     test that hint is not null
>     Meant to be included at end of arch/*/asm/atomic.h files
> 
>  include/linux/atomic.h |   36 ++++++++++++++++++++++++++++++++++++
>  1 files changed, 36 insertions(+)
> 
> diff --git a/include/linux/atomic.h b/include/linux/atomic.h
> new file mode 100644
> index 0000000..0897bdd
> --- /dev/null
> +++ b/include/linux/atomic.h
> @@ -0,0 +1,36 @@
> +#ifndef _LINUX_ATOMIC_H
> +#define _LINUX_ATOMIC_H
> +
> +/**
> + * atomic_inc_not_zero_hint - increment if not null
> + * @v: pointer of type atomic_t
> + * @hint: probable value of the atomic before the increment
> + *
> + * This version of atomic_inc_not_zero() gives a hint of probable
> + * value of the atomic. This helps processor to not read memory
> + * before doing the atomic read/modify/write cycle, lowering
> + * number of bus transactions on some arches.
> + * Note: @hint MUST not be 0, or increment is not done.
> + * Returns: 0 if increment was not done, 1 otherwise.
> + */
> +#ifndef atomic_inc_not_zero_hint
> +static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
> +{
> +	int val, c = hint;
> +
> +	/* sanity test, should be removed by compiler if hint is a constant */
> +	if (!hint)
> +		return 0;

OK, so I cannot resist the challenge...  ;-)

Suppose that the atomic_inc_not_zero_hint() is in common code that might
be invoked from a cleanup path.  On the cleanup path, perhaps within an
RCU callback, if the reference is zero, we have the only reference and
thus don't need to increment the reference count.  On the other hand,
if the reference is non-zero, we want to obtain a reference in order
to safely attempt to encourage the other reference holder to let go
more quickly.

Perhaps a bit of a stretch, but why not just replace the above
"return 0" with "atomic_inc_not_zero(v)"?  It will usually be
compiled out, right?

							Thanx, Paul

> + 	do {
> +		val = atomic_cmpxchg(v, c, c + 1);
> +		if (val == c)
> +			return 1;
> +		c = val;
> +	} while (c);
> +
> +	return 0;
> +}
> +#endif
> +
> +#endif /* _LINUX_ATOMIC_H */
> 
> 

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le vendredi 05 novembre 2010 à 11:40 -0700, Paul E. McKenney a écrit :

> OK, so I cannot resist the challenge...  ;-)
> 

I knew that ;)

> Suppose that the atomic_inc_not_zero_hint() is in common code that might
> be invoked from a cleanup path.  On the cleanup path, perhaps within an
> RCU callback, if the reference is zero, we have the only reference and
> thus don't need to increment the reference count.  On the other hand,
> if the reference is non-zero, we want to obtain a reference in order
> to safely attempt to encourage the other reference holder to let go
> more quickly.
> 
> Perhaps a bit of a stretch, but why not just replace the above
> "return 0" with "atomic_inc_not_zero(v)"?  It will usually be
> compiled out, right?

Yes indeed, thanks !

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le vendredi 05 novembre 2010 à 11:28 -0700, Andrew Morton a écrit :
> But we haven't established that there _is_ duplicated code which needs
> that treatment.
> 
> Scanning arch/x86/include/asm/atomic.h, perhaps ATOMIC_INIT() is a
> candidate.  But I'm not sure that it _should_ be hoisted up - if every
> architecture happens to do it the same way then that's just a fluke.
> 
> 

Not sure I understand you. I was trying to avoid recursive includes, but
that should be protected anyway. I see a lot of code that could be
factorized in this new header (atomic_inc_not_zero() for example)

Thanks

[PATCH v3] atomic: add atomic_inc_not_zero_hint()

Followup of perf tools session in Netfilter WorkShop 2010

In network stack we make high usage of atomic_inc_not_zero() in contexts
we know the probable value of atomic before increment (2 for udp sockets
for example)

Using a special version of atomic_inc_not_zero() giving this hint can
help processor to use less bus transactions.

On x86 (MESI protocol) for example, this avoids entering Shared state,
because "lock cmpxchg" issues an RFO (Read For Ownership)

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Christoph Lameter <cl@linux-foundation.org>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Andi Kleen <andi@firstfloor.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: David Miller <davem@davemloft.net>
Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Cc: Nick Piggin <npiggin@kernel.dk>
---
V3: adds the include <asm/atomic.h>
    if hint is null, use atomic_inc_not_zero() (Paul suggestion)
V2: add #ifndef atomic_inc_not_zero_hint
    kerneldoc changes
    test that hint is not null
    Meant to be included at end of arch/*/asm/atomic.h files

diff --git a/include/linux/atomic.h b/include/linux/atomic.h
new file mode 100644
index 0000000..5a7df87
--- /dev/null
+++ b/include/linux/atomic.h
@@ -0,0 +1,37 @@
+#ifndef _LINUX_ATOMIC_H
+#define _LINUX_ATOMIC_H
+#include <asm/atomic.h>
+
+/**
+ * atomic_inc_not_zero_hint - increment if not null
+ * @v: pointer of type atomic_t
+ * @hint: probable value of the atomic before the increment
+ *
+ * This version of atomic_inc_not_zero() gives a hint of probable
+ * value of the atomic. This helps processor to not read the memory
+ * before doing the atomic read/modify/write cycle, lowering
+ * number of bus transactions on some arches.
+ *
+ * Returns: 0 if increment was not done, 1 otherwise.
+ */
+#ifndef atomic_inc_not_zero_hint
+static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
+{
+	int val, c = hint;
+
+	/* sanity test, should be removed by compiler if hint is a constant */
+	if (!hint)
+		return atomic_inc_not_zero(v);
+
+ 	do {
+		val = atomic_cmpxchg(v, c, c + 1);
+		if (val == c)
+			return 1;
+		c = val;
+	} while (c);
+
+	return 0;
+}
+#endif
+
+#endif /* _LINUX_ATOMIC_H */

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Andrew Morton]

On Fri, 05 Nov 2010 20:20:44 +0100
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> Le vendredi 05 novembre 2010 __ 11:28 -0700, Andrew Morton a __crit :
> > But we haven't established that there _is_ duplicated code which needs
> > that treatment.
> > 
> > Scanning arch/x86/include/asm/atomic.h, perhaps ATOMIC_INIT() is a
> > candidate.  But I'm not sure that it _should_ be hoisted up - if every
> > architecture happens to do it the same way then that's just a fluke.
> > 
> > 
> 
> Not sure I understand you. I was trying to avoid recursive includes, but
> that should be protected anyway. I see a lot of code that could be
> factorized in this new header (atomic_inc_not_zero() for example)

Ah.  I wasn't able to see much duplicated code at all, so I wasn't sure
that we needed to bother about this issue.

yup, atomic_inc_not_zero() looks like a candidate.

> [PATCH v3] atomic: add atomic_inc_not_zero_hint()

Let's go with this for now ;)

I'll assume that you intend to make use of this function soon, and it
looks safe enough to sneak it into 2.6.37-rc2, IMO.  If Linus shouts at
me then we could merge it into 2.6.38-rc1 via net-next, but I think
straight-to-mainline is best.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le vendredi 05 novembre 2010 à 12:39 -0700, Andrew Morton a écrit :

> Ah.  I wasn't able to see much duplicated code at all, so I wasn't sure
> that we needed to bother about this issue.
> 
> yup, atomic_inc_not_zero() looks like a candidate.

yes, and atomic_add_unless()...

> 
> > [PATCH v3] atomic: add atomic_inc_not_zero_hint()
> 
> Let's go with this for now ;)
> 
> I'll assume that you intend to make use of this function soon, and it
> looks safe enough to sneak it into 2.6.37-rc2, IMO.  If Linus shouts at
> me then we could merge it into 2.6.38-rc1 via net-next, but I think
> straight-to-mainline is best.
> 

Well, I dont expect using it before 2.6.38, no hurry Andrew, but it
probably can be merged before, since it has no user yet. It'll help our
job for sure.

Thanks

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Paul E. McKenney]

On Fri, Nov 05, 2010 at 08:20:44PM +0100, Eric Dumazet wrote:
> Le vendredi 05 novembre 2010 à 11:28 -0700, Andrew Morton a écrit :
> > But we haven't established that there _is_ duplicated code which needs
> > that treatment.
> > 
> > Scanning arch/x86/include/asm/atomic.h, perhaps ATOMIC_INIT() is a
> > candidate.  But I'm not sure that it _should_ be hoisted up - if every
> > architecture happens to do it the same way then that's just a fluke.
> > 
> > 
> 
> Not sure I understand you. I was trying to avoid recursive includes, but
> that should be protected anyway. I see a lot of code that could be
> factorized in this new header (atomic_inc_not_zero() for example)
> 
> Thanks
> 
> [PATCH v3] atomic: add atomic_inc_not_zero_hint()
> 
> Followup of perf tools session in Netfilter WorkShop 2010
> 
> In network stack we make high usage of atomic_inc_not_zero() in contexts
> we know the probable value of atomic before increment (2 for udp sockets
> for example)
> 
> Using a special version of atomic_inc_not_zero() giving this hint can
> help processor to use less bus transactions.
> 
> On x86 (MESI protocol) for example, this avoids entering Shared state,
> because "lock cmpxchg" issues an RFO (Read For Ownership)
> 
> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
> Cc: Christoph Lameter <cl@linux-foundation.org>
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Andi Kleen <andi@firstfloor.org>
> Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
> Cc: David Miller <davem@davemloft.net>
> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

Looks quite good to me!

Reviewed-by: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

> Cc: Nick Piggin <npiggin@kernel.dk>
> ---
> V3: adds the include <asm/atomic.h>
>     if hint is null, use atomic_inc_not_zero() (Paul suggestion)
> V2: add #ifndef atomic_inc_not_zero_hint
>     kerneldoc changes
>     test that hint is not null
>     Meant to be included at end of arch/*/asm/atomic.h files
> 
> diff --git a/include/linux/atomic.h b/include/linux/atomic.h
> new file mode 100644
> index 0000000..5a7df87
> --- /dev/null
> +++ b/include/linux/atomic.h
> @@ -0,0 +1,37 @@
> +#ifndef _LINUX_ATOMIC_H
> +#define _LINUX_ATOMIC_H
> +#include <asm/atomic.h>
> +
> +/**
> + * atomic_inc_not_zero_hint - increment if not null
> + * @v: pointer of type atomic_t
> + * @hint: probable value of the atomic before the increment
> + *
> + * This version of atomic_inc_not_zero() gives a hint of probable
> + * value of the atomic. This helps processor to not read the memory
> + * before doing the atomic read/modify/write cycle, lowering
> + * number of bus transactions on some arches.
> + *
> + * Returns: 0 if increment was not done, 1 otherwise.
> + */
> +#ifndef atomic_inc_not_zero_hint
> +static inline int atomic_inc_not_zero_hint(atomic_t *v, int hint)
> +{
> +	int val, c = hint;
> +
> +	/* sanity test, should be removed by compiler if hint is a constant */
> +	if (!hint)
> +		return atomic_inc_not_zero(v);
> +
> + 	do {
> +		val = atomic_cmpxchg(v, c, c + 1);
> +		if (val == c)
> +			return 1;
> +		c = val;
> +	} while (c);
> +
> +	return 0;
> +}
> +#endif
> +
> +#endif /* _LINUX_ATOMIC_H */
> 
> 

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Christoph Lameter]

prefetchw() would be too much overhead?

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Paul E. McKenney]

On Fri, Nov 12, 2010 at 01:14:12PM -0600, Christoph Lameter wrote:
> 
> prefetchw() would be too much overhead?

No idea.  Where do you believe that prefetchw() should be added?

							Thanx, Paul

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Christoph Lameter]

On Sat, 13 Nov 2010, Paul E. McKenney wrote:

> On Fri, Nov 12, 2010 at 01:14:12PM -0600, Christoph Lameter wrote:
> >
> > prefetchw() would be too much overhead?
>
> No idea.  Where do you believe that prefetchw() should be added?

It is another way to get an exclusive cache line
for situations like this. No need to give a hint.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Andi Kleen]

On Mon, Nov 15, 2010 at 07:57:10AM -0600, Christoph Lameter wrote:
> On Sat, 13 Nov 2010, Paul E. McKenney wrote:
> 
> > On Fri, Nov 12, 2010 at 01:14:12PM -0600, Christoph Lameter wrote:
> > >
> > > prefetchw() would be too much overhead?
> >
> > No idea.  Where do you believe that prefetchw() should be added?
> 
> It is another way to get an exclusive cache line
> for situations like this. No need to give a hint.

prefetchw doesn't work on Intel (or rather is equivalent to prefetch), 
for Intel you always need to explicitely write to get an exclusive
line.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Christoph Lameter]

On Mon, 15 Nov 2010, Andi Kleen wrote:

> > It is another way to get an exclusive cache line
> > for situations like this. No need to give a hint.
>
> prefetchw doesn't work on Intel (or rather is equivalent to prefetch),
> for Intel you always need to explicitely write to get an exclusive
> line.

Argh. You mean x86. Itanium could do it and is also by Intel. Could you
please change that for x86 as well? Otherwise we will get more of these
weird code twisters.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le lundi 15 novembre 2010 à 07:57 -0600, Christoph Lameter a écrit :
> On Sat, 13 Nov 2010, Paul E. McKenney wrote:
> 
> > On Fri, Nov 12, 2010 at 01:14:12PM -0600, Christoph Lameter wrote:
> > >
> > > prefetchw() would be too much overhead?
> >
> > No idea.  Where do you believe that prefetchw() should be added?
> 
> It is another way to get an exclusive cache line
> for situations like this. No need to give a hint.
> 

Exclusive access ? As soon as another cpu takes it again, you lose.

Its not really the same thing... Maybe you miss the 'hint' intention at
all. We know the probable value of the counter, we dont want to read it.

In fact, prefetchw() is useful when you can assert it many cycles before
the memory read you are going to perform [before the write]. On
contended cache lines, its a waste, because by the time your cpu is
going to read memory, then perform the atomic compare_and_exchange(), an
other cpu might have dirtied the location again. This is what we noticed
during Netfilter Workshop 2010 : A high performance cost at both
atomic_read() and atomic_cmpxchg(). We tried prefetchw() and it was a
performance drop. It was with only 16 cpus contending on neighbour
refcnt, and 5 millions frames per second (5 millions atomic increments,
5 millions atomic decrements)

prefetchw() should be used on very specific spots, when a cpu is going
to write into a private area (not potentially accessed by other cpus).
We use it for example in __alloc_skb(), a bit before memset().

By the way, atomic_inc_not_zero_hint() is less code than 
[prefetchw(), atomic_inc_not_zero()]. Using one instruction [cmpxchg]
with the memory pointer is better than three.  [prefetchw(), read(),
cmpxchg()], particularly if you have high contention on cache line.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Christoph Lameter]

On Mon, 15 Nov 2010, Eric Dumazet wrote:

> Exclusive access ? As soon as another cpu takes it again, you lose.

Sure but you want to avoid the fetch in shared mode here.

> Its not really the same thing... Maybe you miss the 'hint' intention at
> all. We know the probable value of the counter, we dont want to read it.

Ok may be in thise case you can predict the value but in general it is
difficult to always provide an expected value. It would be easier to be
able to tell the processor that the cacheline should not be fetched as
shared but immediately in exclusive state.

> atomic_read() and atomic_cmpxchg(). We tried prefetchw() and it was a
> performance drop. It was with only 16 cpus contending on neighbour

Does prefetchw work? Andi claims that prefetchw is not working on
x86 and I doubt that you ran tests on Itanium.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Andi Kleen]

> > atomic_read() and atomic_cmpxchg(). We tried prefetchw() and it was a
> > performance drop. It was with only 16 cpus contending on neighbour
> 
> Does prefetchw work? Andi claims that prefetchw is not working on
> x86 and I doubt that you ran tests on Itanium.

AMD supports it due to their MOESI protocol, but it's not supported
in MESIF as used by Intel QPI.  The kernel maps it on Intel to 
ordinary prefetch.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] atomic: add atomic_inc_not_zero_hint()

[Eric Dumazet]

Le lundi 15 novembre 2010 à 08:25 -0600, Christoph Lameter a écrit :
> On Mon, 15 Nov 2010, Eric Dumazet wrote:
> 
> > Exclusive access ? As soon as another cpu takes it again, you lose.
> 
> Sure but you want to avoid the fetch in shared mode here.
> 

Yes, this is what cmpxchg() does for sure.

> > Its not really the same thing... Maybe you miss the 'hint' intention at
> > all. We know the probable value of the counter, we dont want to read it.
> 
> Ok may be in thise case you can predict the value but in general it is
> difficult to always provide an expected value. It would be easier to be
> able to tell the processor that the cacheline should not be fetched as
> shared but immediately in exclusive state.
> 

Maybe its not clear, but atomic_inc_not_zero_hint() is going to be used
only in contexts we know the expected value, and not as a generic
replacement for atomic_inc_not_zero(). Even if cache line is already hot
in this cpu cache, it should be faster or same speed.

Then, in high contention contexts, using atomic_inc_not_zero_hint() with
whatever initial hint might also be a win over atomic_inc_not_zero(),
but we try to remove such contexts ;)

And two atomic_cmpxchg() are probably slower in non contended contexts,
in particular is cache line is already hot in this cpu cache.

> > atomic_read() and atomic_cmpxchg(). We tried prefetchw() and it was a
> > performance drop. It was with only 16 cpus contending on neighbour
> 
> Does prefetchw work? Andi claims that prefetchw is not working on
> x86 and I doubt that you ran tests on Itanium.

In fact, in benchmarks, prefetch() or prefetchw() are a pain on x86, or
at least "perf tools" show artifact on them (high number of cycles
consumed on these instructions)

Andi had a patch to disable prefetch() in list iterators, and its a win.

I dont have Itanium platform to run tests. Is cmpxchg() that bad on
ia64 ? I also have old AMD cpus, so I cannot say if recent ones handle
prefetchw() better...