[PATCH] arp_queue: serializing unlink + kfree_skb

[PATCH] arp_queue: serializing unlink + kfree_skb

[Olaf Kirch]

[-- Attachment #1: Type: text/plain, Size: 2575 bytes --]

Hi,

I'm just looking into a problem that may be related to the
new neighbor discovery code in core/neighbour.c.

The problem was originally reported against our SLES kernel, but the
code in 2.6.11-rc2 is almost identical; code and patches shown below
are relative to 2.6.11-rc2

The problem is that IBM testing was hitting the assertion in kfree_skb
that checks that the skb has been removed from any list it was on
("kfree_skb passed an skb still on a list").

It seems the problem is a bad interaction between neigh_event_send and
neigh_timer_handler:

In neigh_event_send:

		if (skb_queue_len(&neigh->arp_queue) >=
		    neigh->parms->queue_len) {
			struct sk_buff *buff;
			buff = neigh->arp_queue.next;
			__skb_unlink(buff, &neigh->arp_queue);
			kfree_skb(buff);
		}

If the ARP queue overflows, we're trying to remove the first skb
from the list. While we do this, the neighbor is locked.

The corresponding piece of code in neigh_timer_handler is this:

                struct sk_buff *skb = skb_peek(&neigh->arp_queue);
                /* keep skb alive even if arp_queue overflows */
                if (skb)
                        skb_get(skb);
                write_unlock(&neigh->lock);
                neigh->ops->solicit(neigh, skb);
                atomic_inc(&neigh->probes);
                if (skb)
                        kfree_skb(skb); /* <== this is where we BUG() */

The use of skb_get/kfree_skb makes sure the skb remains live while
we're calling solicit(). Note that the neighbor isn't locked when we
call kfree_skb.

Now what happens in the bug that was reported to us (this was on a
PPC SMP machine) is this, I think:

 -	On CPU 0, neigh_timer_handler grabs the first skb on the queue,
	incrementing is reference count to 2,
	unlocks the neighbor, calls solicit()
 -	On CPU 1, we enter neigh_event_send, find the ARP
	queue is full and remove the first skb. The call to kfree_skb
	will decrement the refcount to 1. This change is visible
	on all CPUs immediately, because it's an atomic_dec.
	The effects of __skb_unlink are not immediately visible
	on the other CPUs however.
 -	On the first CPU, we return from solicit, call kfree_skb.
 	Refcount goes to zero, but __kfree_skb still sees the
	skb->list pointer => barf.

One possible fix here would be to add an smp_wmb after the __skb_unlink
and a smp_rmb before the assertion in __kfree_skb, as in the attached
patch.

Does this make sense?

Olaf
-- 
Olaf Kirch   |  --- o --- Nous sommes du soleil we love when we play
okir@suse.de |    / | \   sol.dhoop.naytheet.ah kin.ir.samse.qurax

[-- Attachment #2: arp-skb-unlink-serialize --]
[-- Type: text/plain, Size: 1103 bytes --]

Index: linux-2.6.10/net/core/neighbour.c
===================================================================
--- linux-2.6.10.orig/net/core/neighbour.c	2005-01-21 11:04:23.000000000 +0100
+++ linux-2.6.10/net/core/neighbour.c	2005-01-31 11:20:38.000000000 +0100
@@ -876,6 +876,9 @@ int __neigh_event_send(struct neighbour 
 				struct sk_buff *buff;
 				buff = neigh->arp_queue.next;
 				__skb_unlink(buff, &neigh->arp_queue);
+				/* Make sure the change of skb->head is
+				 * visible on all CPUs */
+				smp_wmb();
 				kfree_skb(buff);
 			}
 			__skb_queue_tail(&neigh->arp_queue, skb);
Index: linux-2.6.10/net/core/skbuff.c
===================================================================
--- linux-2.6.10.orig/net/core/skbuff.c	2005-01-21 11:04:15.000000000 +0100
+++ linux-2.6.10/net/core/skbuff.c	2005-01-31 11:20:52.000000000 +0100
@@ -275,6 +275,7 @@ void kfree_skbmem(struct sk_buff *skb)
 
 void __kfree_skb(struct sk_buff *skb)
 {
+	smp_rmb();
 	if (skb->list) {
 	 	printk(KERN_WARNING "Warning: kfree_skb passed an skb still "
 		       "on a list (from %p).\n", NET_CALLER(skb));

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

Olaf Kirch <okir@suse.de> wrote:
> 
> The problem is that IBM testing was hitting the assertion in kfree_skb
> that checks that the skb has been removed from any list it was on
> ("kfree_skb passed an skb still on a list").

That must've be some testing to catch this :)
 
> One possible fix here would be to add an smp_wmb after the __skb_unlink
> and a smp_rmb before the assertion in __kfree_skb, as in the attached
> patch.
> 
> Does this make sense?

It makes sense.  However, I'm not sure whether we want to add a read
barrier to the common path in kfree_skb just for a debugging test.
If it was only for the skb->list test we could move the read barrier
inside the if and reread skb->list if it were non-NULL.

What you've done is expose a much bigger problem in Linux.  We're
using atomic integers to signal that we're done with an object.
The object is usually represented by a piece of memory.

The problem is that in most of the places where we do this (and that's
not just in the networking systems), there are no memory barriers between
the last reference to that object and the decrease on the atomic counter.

For example, in this particular case, a more sinister (but probably
impossible for sk_buff objects) problem would be for the list removal
itself to be delayed until after the the kfree_skb.  This could
potentially mean that we're reading/writing memory that's already
been freed.

Perhaps we should always add a barrier to such operations.  So
kfree_skb would become

	if (atomic_read(&skb->users) != 1) {
		smp_mb__before_atomic_dec();
		if (!atomic_dec_and_test(&skb->users))
			return;
	}
	__kfree_skb(skb);

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Mon, 31 Jan 2005 22:33:26 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> We're using atomic integers to signal that we're done with an object.
> The object is usually represented by a piece of memory.
> 
> The problem is that in most of the places where we do this (and that's
> not just in the networking systems), there are no memory barriers between
> the last reference to that object and the decrease on the atomic counter.

I agree.

> 	if (atomic_read(&skb->users) != 1) {
> 		smp_mb__before_atomic_dec();
> 		if (!atomic_dec_and_test(&skb->users))
> 			return;
> 	}
> 	__kfree_skb(skb);

This looks good.  Olaf can you possibly ask the reproducer if
this patch makes the ARP problem go away?

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2005/02/02 15:53:55-08:00 herbert@gondor.apana.org.au 
#   [NET]: Add missing memory barrier to SKB release.
#   
#   Here, we are using atomic counters to signal that we are done
#   with an object.  The object is usually represented by a piece
#   of memory.
#   
#   The problem is that in most of the places we do this, there are
#   no memory barriers between the last reference to that object
#   and the decrease on the atomic counter.
#   
#   Based upon a race spotted in arp_queue handling by Olaf Kirch.
#   
#   Signed-off-by: David S. Miller <davem@davemloft.net>
# 
# include/linux/skbuff.h
#   2005/02/02 15:51:57-08:00 herbert@gondor.apana.org.au +6 -2
#   [NET]: Add missing memory barrier to SKB release.
# 
diff -Nru a/include/linux/skbuff.h b/include/linux/skbuff.h
--- a/include/linux/skbuff.h	2005-02-02 15:54:13 -08:00
+++ b/include/linux/skbuff.h	2005-02-02 15:54:13 -08:00
@@ -353,8 +353,12 @@
  */
 static inline void kfree_skb(struct sk_buff *skb)
 {
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
-		__kfree_skb(skb);
+	if (atomic_read(&skb->users) != 1) {
+		smp_mb__before_atomic_dec();
+		if (!atomic_dec_and_test(&skb->users))
+			return;
+	}
+	__kfree_skb(skb);
 }
 
 /* Use this if you didn't touch the skb state [for fast switching] */

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

[-- Attachment #1: Type: text/plain, Size: 1699 bytes --]

On Wed, Feb 02, 2005 at 04:20:23PM -0800, David S. Miller wrote:
> 
> > 	if (atomic_read(&skb->users) != 1) {
> > 		smp_mb__before_atomic_dec();
> > 		if (!atomic_dec_and_test(&skb->users))
> > 			return;
> > 	}
> > 	__kfree_skb(skb);
> 
> This looks good.  Olaf can you possibly ask the reproducer if
> this patch makes the ARP problem go away?

Not so hasty Dave :)

That was only meant to be an example of what we might do to
insert a write barrier in kfree_skb().

It doesn't solve Olaf's problem because a write barrier is
usually not sufficient by itself.  In most cases you'll need
a read barrier as well.

So if we're going for a solution that only involves kfree_skb()
then we'll need the following patch.

I got rid of the atomic_read optimisation since it would've needed
an additional smp_rmb() to be safe.

I thought about preserving that optimisation through something
like skb->cloned.  However, it turns out that most skb's will be
shared at least once so it doesn't buy us much.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

What I hoped to do though was to bring your collective attention
to the problem in general.  kfree_skb() is certainly not the only
place where we free an object after the counter hits zero.

This paradigm is repeated throughout the kernel.  I bet the
same race can be found in a lot of those places.  So we really
need to sit down and audit them one by one or else come up with
a magical solution apart from disabling SMP :) 

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[-- Attachment #2: p --]
[-- Type: text/plain, Size: 852 bytes --]

===== include/linux/skbuff.h 1.59 vs edited =====
--- 1.59/include/linux/skbuff.h	2005-01-11 07:23:55 +11:00
+++ edited/include/linux/skbuff.h	2005-02-03 21:57:26 +11:00
@@ -353,15 +353,21 @@
  */
 static inline void kfree_skb(struct sk_buff *skb)
 {
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
-		__kfree_skb(skb);
+	smp_mb__before_atomic_dec();
+	if (!atomic_dec_and_test(&skb->users))
+		return;
+	smp_mb__after_atomic_dec();
+	__kfree_skb(skb);
 }
 
 /* Use this if you didn't touch the skb state [for fast switching] */
 static inline void kfree_skb_fast(struct sk_buff *skb)
 {
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
-		kfree_skbmem(skb);
+	smp_mb__before_atomic_dec();
+	if (!atomic_dec_and_test(&skb->users))
+		return;
+	smp_mb__after_atomic_dec();
+	kfree_skbmem(skb);
 }
 
 /**

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Thu, 3 Feb 2005 22:12:24 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> This paradigm is repeated throughout the kernel.  I bet the
> same race can be found in a lot of those places.  So we really
> need to sit down and audit them one by one or else come up with
> a magical solution apart from disabling SMP :) 

Ok.  I'm commenting now considering Anton's atomic_t rules.
Anton, please read down below, I think there is a hole in the
PPC memory barriers used for atomic ops on SMP.

I don't see what changes are needed anywhere given those
rules.  Olaf says the problem shows up on PPC SMP system,
and since Anton knows the proper rules we hopefully can
safely assume he implemented them correctly on PPC :-)

I thought for a moment that the atomic_read() might be
an issue, and I'd really hate to kill that optimization.
But I can't see how it is.  Let us restate Olaf's original
guess as to the problematic sequence of events:

	cpu 0			cpu 1
	skb_get(skb)
	unlock(neigh)
				lock(neigh)
				__skb_unlink(skb)
				kfree_skb(sb)
	kfree_skb(skb)

First, __skb_unlink(skb) does an unlocked queue unlink, and
these memory operations may have their visibility freely reordered
by the processor.

However, cpu 1 will see the refcount at 2, so it will execute:

	atomic_dec_and_test(&skb->users)

which has the implicit memory barriers, as Anton stated.  This
means that the cpu will make the __skb_unlink(skb) results visible
globally before the decrement.

Now the kfree_skb() on cpu 0 executes, the atomic_read() sees it
at 1, we do the __kfree_skb() and since the __skb_unlink() has been
made visible before the decrement on the count to "1" the BUG()
should not trigger in __kfree_skb().

This all assumes, again, that PPC implements these things properly.

Let's take a look (Anton, start reading here).  My understanding of PPC
memory barriers, wrt. the physical memory coherency domain, is as follows:

	sync	! All previous read/write execute before all subsequent read/write
	lwsync	! All previous reads execute before all subsequent read/write
	eieio	! All previous writes execute before all subsequent read/write
	isync	! All previous memory operations and instructions execute and
		! reach global visibility before any subsequent instructions execute

What guarentees does isync really make about "read" reordering around
the atomic increment?  Any descrepencies here would account for the
case Olaf observed.

All the atomic ops returning values on PPC do this on SMP:

	eieio
	atomic_op()
	isync

At a minimum, it seems that the eieio is not strong enough a
memory barrier.  It is defined to order previous writes against
future memory operations, but we also need to strictly order
previous reads as well don't we?

Also, if my understanding of isync is not correct, that could
have implications as well.

I guess for performance reasons, ppc doesn't use "sync" both
before and after the atomic ops requiring ordering.  But I
suspect that might be what is actually needed for proper conformity
to the atomic_t memory ordering rules.

Anton?

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Anton Blanchard]

 
Hi,

> For example, in this particular case, a more sinister (but probably
> impossible for sk_buff objects) problem would be for the list removal
> itself to be delayed until after the the kfree_skb.  This could
> potentially mean that we're reading/writing memory that's already
> been freed.
> 
> Perhaps we should always add a barrier to such operations.  So
> kfree_skb would become
> 
> 	if (atomic_read(&skb->users) != 1) {
> 		smp_mb__before_atomic_dec();
> 		if (!atomic_dec_and_test(&skb->users))
> 			return;
> 	}
> 	__kfree_skb(skb);

Architectures should guarantee that any of the atomics and bitops that
return values order in both directions. So you dont need the
smp_mb__before_atomic_dec here.

It is, however, required on the atomics and bitops that dont return
values. Its difficult stuff, everyone gets it wrong and Andrew keeps
hassling me to write up a document explaining it.

Anton

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 01:27:05 +1100
Anton Blanchard <anton@samba.org> wrote:

> Architectures should guarantee that any of the atomics and bitops that
> return values order in both directions. So you dont need the
> smp_mb__before_atomic_dec here.
> 
> It is, however, required on the atomics and bitops that dont return
> values. Its difficult stuff, everyone gets it wrong and Andrew keeps
> hassling me to write up a document explaining it.

Sparc64 happens to order the atomic we use in the bitops and atomic_t
ops, so sparc64 gets this right by accident.

I had no idea about this requirement before reading your email.

If IBM is seeing race this on ppc64, then I'm even more confused.
If Anton understands the requirements, then ppc64 should have
the return value atomic's implemented with the proper barriers.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

On Fri, Feb 04, 2005 at 01:27:05AM +1100, Anton Blanchard wrote:
> 
> Architectures should guarantee that any of the atomics and bitops that
> return values order in both directions. So you dont need the
> smp_mb__before_atomic_dec here.

I wasn't aware of this requirement before.  However, if this is so,
why don't we get rid of the smp_mb__* macros?

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 07:30:10 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> On Fri, Feb 04, 2005 at 01:27:05AM +1100, Anton Blanchard wrote:
> > 
> > Architectures should guarantee that any of the atomics and bitops that
> > return values order in both directions. So you dont need the
> > smp_mb__before_atomic_dec here.
> 
> I wasn't aware of this requirement before.  However, if this is so,
> why don't we get rid of the smp_mb__* macros?

They are for cases where you want strict ordering even for the
non-return-value-giving atomic_t ops.

Actually.... Herbert has a point.  By Anton's specification, several
uses in 2.6.x I see of these smp_mb__*() routines are bogus.  Case
in point, look at mm/filemap.c:

void fastcall unlock_page(struct page *page)
{
	smp_mb__before_clear_bit();
	if (!TestClearPageLocked(page))
		BUG();
	smp_mb__after_clear_bit(); 
	wake_up_page(page, PG_locked);
}

TestClearPageLocked() uses one of the bitops returning a value, so
must be providing the explicit memory barriers in it's implementation.

void end_page_writeback(struct page *page)
{
	if (!TestClearPageReclaim(page) || rotate_reclaimable_page(page)) {
		if (!test_clear_page_writeback(page))
			BUG();
	}
	smp_mb__after_clear_bit();
	wake_up_page(page, PG_writeback);
}

Same thing there.

Looking at include/linux/sunrpc/sched.h, those uses are legitimate,
correct, and needed.  As is the put_bh() use in include/linux/buffer_head.h
There are several other correct and necessary uses in:

	include/linux/interrupt.h
	include/linux/netdevice.h
	include/linux/nfs_page.h
	include/linux/spinlock.h
	net/core/dev.c
	net/sunrpc/sched.c
	sound/pci/bt87x.c
	fs/buffer.c
	fs/nfs/pagelist.c
	drivers/block/ll_rw_blk.c
	arch/ppc64/kernel/smp.c
	arch/i386/kernel/smp.c
	arch/i386/mach-voyager/smp.c

I'm working on a rough but rather complete draft Anton said needs
to be written to explicitly spell out the atomic_t and bitops
stuff.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

[-- Attachment #1: Type: text/plain, Size: 844 bytes --]

On Thu, Feb 03, 2005 at 02:19:01PM -0800, David S. Miller wrote:
> 
> They are for cases where you want strict ordering even for the
> non-return-value-giving atomic_t ops.

I see.  I got atomic_dec and atomic_dec_and_test mixed up.

So the problem isn't as big as I thought which is good.  sk_buff
is only in trouble because of the atomic_read optimisation which
really needs a memory barrier.

However, instead of adding a memory barrier which makes the optimisation
less useful, let's just get rid of the atomic_read.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Thanks for the document, it's really helpful.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[-- Attachment #2: p --]
[-- Type: text/plain, Size: 660 bytes --]

===== include/linux/skbuff.h 1.59 vs edited =====
--- 1.59/include/linux/skbuff.h	2005-01-11 07:23:55 +11:00
+++ edited/include/linux/skbuff.h	2005-02-04 10:44:17 +11:00
@@ -353,14 +353,14 @@
  */
 static inline void kfree_skb(struct sk_buff *skb)
 {
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
+	if (atomic_dec_and_test(&skb->users))
 		__kfree_skb(skb);
 }
 
 /* Use this if you didn't touch the skb state [for fast switching] */
 static inline void kfree_skb_fast(struct sk_buff *skb)
 {
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
+	if (atomic_dec_and_test(&skb->users))
 		kfree_skbmem(skb);
 }
 

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 10:50:44 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> So the problem isn't as big as I thought which is good.  sk_buff
> is only in trouble because of the atomic_read optimisation which
> really needs a memory barrier.
> 
> However, instead of adding a memory barrier which makes the optimisation
> less useful, let's just get rid of the atomic_read.

See my other email, the atomic_read() should function just fine.

If we see the count dropped to "1", whoever set it to "1" made
sure that all outstanding memory operations (including things
like __skb_unlink()) are globally visible before the
atomic_dec_and_test() which put the thing to "1" from "2".
(and we did use atomic_dec_and_test() since the refcount was
 not "1")  Example, assuming skb->users is "2":

	cpu 0			cpu 1
				__skb_unlink()
				kfree_skb()
	kfree_skb()

If cpu 0 sees the count at "1", it will always see the
__skb_unlink() as well.

Either my logic is flawed (very possible, I am a pinhead) or something
is amiss in the PPC atomic ops.

I describe all of this more explicitly in my other email.
I'm actually going through all the sparc64 chip manuals to make
sure I have things correct in that implementation :-)))

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

On Thu, Feb 03, 2005 at 04:49:22PM -0800, David S. Miller wrote:
> 
> If we see the count dropped to "1", whoever set it to "1" made
> sure that all outstanding memory operations (including things
> like __skb_unlink()) are globally visible before the
> atomic_dec_and_test() which put the thing to "1" from "2".
> (and we did use atomic_dec_and_test() since the refcount was
>  not "1")  Example, assuming skb->users is "2":
> 
> 	cpu 0			cpu 1
> 				__skb_unlink()
> 				kfree_skb()
> 	kfree_skb()
> 
> If cpu 0 sees the count at "1", it will always see the
> __skb_unlink() as well.

This is true if CPU 0 reads the count before reading skb->list.
Without a memory barrier, atomic_read and reading skb->list can
be reordered.  Put it another way, reading skb->list could return
a cached value that was read from the main memory prior to the
atomic_read.

So in order for CPU 0 to always see an up-to-date value of skb->list,
it needs to do an smp_rmb() between the atomic_read and reading
skb->list.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 12:20:53 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> This is true if CPU 0 reads the count before reading skb->list.
> Without a memory barrier, atomic_read and reading skb->list can
> be reordered.  Put it another way, reading skb->list could return
> a cached value that was read from the main memory prior to the
> atomic_read.
> 
> So in order for CPU 0 to always see an up-to-date value of skb->list,
> it needs to do an smp_rmb() between the atomic_read and reading
> skb->list.

You're absolutely right.  Ok, so we do need to change kfree_skb().
I believe even with the memory barrier, the atomic_read() optimization
is still worth it.  atomic ops on sparc64 take a minimum of 40 some odd
cycles on UltraSPARC-III and later, whereas the memory barrier will
take up a single cycle most of the time.

So it'll look something like:

	if (atomic_read(&skb->users) == 1)
		smb_rmb();
	else if (!atomic_dec_and_test(&skb->users))
		return;
	__kfree_skb(skb);

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

[-- Attachment #1: Type: text/plain, Size: 786 bytes --]

On Thu, Feb 03, 2005 at 05:23:57PM -0800, David S. Miller wrote:
> 
> You're absolutely right.  Ok, so we do need to change kfree_skb().
> I believe even with the memory barrier, the atomic_read() optimization
> is still worth it.  atomic ops on sparc64 take a minimum of 40 some odd
> cycles on UltraSPARC-III and later, whereas the memory barrier will
> take up a single cycle most of the time.

OK, here is the patch to do that.  Let's get rid of kfree_skb_fast
while we're at it since it's no longer used.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Thanks,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[-- Attachment #2: p --]
[-- Type: text/plain, Size: 729 bytes --]

===== include/linux/skbuff.h 1.59 vs edited =====
--- 1.59/include/linux/skbuff.h	2005-01-11 07:23:55 +11:00
+++ edited/include/linux/skbuff.h	2005-02-04 12:46:15 +11:00
@@ -353,15 +353,11 @@
  */
 static inline void kfree_skb(struct sk_buff *skb)
 {
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
-		__kfree_skb(skb);
-}
-
-/* Use this if you didn't touch the skb state [for fast switching] */
-static inline void kfree_skb_fast(struct sk_buff *skb)
-{
-	if (atomic_read(&skb->users) == 1 || atomic_dec_and_test(&skb->users))
-		kfree_skbmem(skb);
+	if (likely(atomic_read(&skb->users) == 1))
+		smp_rmb();
+	else if (likely(!atomic_dec_and_test(&skb->users)))
+		return;
+	__kfree_skb(skb);
 }
 
 /**

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Olaf Kirch]

On Fri, Feb 04, 2005 at 12:55:39PM +1100, Herbert Xu wrote:
> OK, here is the patch to do that.  Let's get rid of kfree_skb_fast
> while we're at it since it's no longer used.

Thanks, I'll give that to the PPC folks and ask the to run with it.

Regards,
Olaf
-- 
Olaf Kirch   |  --- o --- Nous sommes du soleil we love when we play
okir@suse.de |    / | \   sol.dhoop.naytheet.ah kin.ir.samse.qurax

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 12:55:39 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> OK, here is the patch to do that.  Let's get rid of kfree_skb_fast
> while we're at it since it's no longer used.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

I've queued this up for 2.6.x and 2.4.x, thanks everyone.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 01:27:05 +1100
Anton Blanchard <anton@samba.org> wrote:

> Its difficult stuff, everyone gets it wrong and Andrew keeps
> hassling me to write up a document explaining it.

Ok, here goes nothing.  Can someone run with this?  It should
be rather complete, and require only minor editorial work.

--- atomic_ops.txt ---

	This document is intended to serve as a guide to Linux port
maintainers on how to implement atomic counter and bitops operations
properly.

	The atomic_t type should be defined as a signed integer.
Also, it should be made opaque such that any kind of cast to
a normal C integer type will fail.  Something like the following
should suffice:

	typedef struct { volatile int counter; } atomic_t;

	The first operations to implement for atomic_t's are
the initializers and plain reads.

	#define ATOMIC_INIT(i)		{ (i) }
	#define atomic_set(v, i)	((v)->counter = (i))

The first macro is used in definitions, such as:

static atomic_t my_counter = ATOMIC_INIT(1);

The second interface can be used at runtime, as in:

	k = kmalloc(sizeof(*k), GFP_KERNEL);
	if (!k)
		return -ENOMEM;
	atomic_set(&k->counter, 0);

Next, we have:

	#define atomic_read(v)	((v)->counter)

which simply reads the current value of the counter.

Now, we move onto the actual atomic operation interfaces.

	void atomic_add(int i, atomic_t *v);
	void atomic_sub(int i, atomic_t *v);
	void atomic_inc(atomic_t *v);
	void atomic_dec(atomic_t *v);

These four routines add and subtract integral values to/from the given
atomic_t value.  The first two routines pass explicit integers by
which to make the adjustment, whereas the latter two use an implicit
adjustment value of "1".

One very important aspect of these two routines is that
they DO NOT require any explicit memory barriers.  They
need only perform the atomic_t counter update in an SMP
safe manner.

Next, we have:

	int atomic_inc_return(atomic_t *v);
	int atomic_dec_return(atomic_t *v);

These routines add 1 and subtract 1, respectively, from
the given atomic_t and return the new counter value after
the operation is performed.

Unlike the above routines, it is required that explicit memory
barriers are performed before and after the operation.  It must
be done such that all memory operations before and after the
atomic operation calls are strongly ordered with respect to the
atomic operation itself.

For example, it should behave as if a smp_mb() call existed both
before and after the atomic operation.

If the atomic instructions used in an implementation provide
explicit memory barrier semantics which satisfy the above requirements,
that is fine as well.

Let's move on:

	int atomic_add_return(int i, atomic_t *v);
	int atomic_sub_return(int i, atomic_t *v);

These behave just like atomic_{inc,dec}_return() except that an
explicit counter adjustment is given instead of the implicit "1".
This means that like atomic_{inc,dec}_return(), the memory barrier
semantics are required.

Next:

	int atomic_inc_and_test(atomic_t *v);
	int atomic_dec_and_test(atomic_t *v);

These two routines increment and decrement by 1, respectively,
the given atomic counter.  They return a boolean indicating
whether the resulting counter value was zero or not.

It requires explicit memory barrier semantics around the operation
as above.

	int atomic_sub_and_test(int i, atomic_t *v);

This is identical to atomic_dec_and_test() except that an explicit
decrement is given instead of the implicit "1".  It requires explicit
memory barrier semantics around the operation.

	int atomic_add_negative(int i, atomic_t *v);

The given increment is added to the given atomic counter value.
A boolean is return which indicates whether the resulting counter
value is negative.  It requires explicit memory barrier semantics
around the operation.

If a caller requires memory barrier semantics around an atomic_t
operation which does not return a value, a set of interfaces
are defined which accomplish this:

	void smb_mb__before_atomic_dec(void);
	void smb_mb__after_atomic_dec(void);
	void smb_mb__before_atomic_inc(void);
	void smb_mb__after_atomic_dec(void);

For example, smb_mb__before_atomic_dec() can be used like so:

	obj->dead = 1;
	smb_mb__before_atomic_dec();
	atomic_dec(&obj->ref_count);

It makes sure that all memory operations preceeding the atomic_dec()
call are strongly ordered with respect to the atomic counter
operation.  In the above example, it guarentees that the assignment
of "1" to obj->dead will be globally visible to other cpus before
the atomic counter decrement.

Without the explicitl smb_mb__before_atomic_dec() call, the
implementation could legally allow the atomic counter update
visible to other cpus before the "obj->dead = 1;" assignment.

The other three interfaces listed are used to provide explicit
ordering with respect to memory operations after an atomic_dec()
call (smb_mb__after_atomic_dec()) and around atomic_inc() calls
(smb_mb__{before,after}_atomic_inc()).

A missing memory barrier in the cases where they are required
by the atomic_t implementation above can have disasterous
results.  Here is an example, which follows a pattern occuring
frequently in the Linux kernel.  It is the use of atomic counters
to implement reference counting, and it works such that once
the counter falls to zero it can be guarenteed that no other
entity can be accessing the object.   Observe:

	list_del(&obj->list);
	if (atomic_dec_and_test(&obj->ref_count))
		kfree(obj);

Here, the list (say it is some linked list on which object
searches are performed) creates the reference to the object.
The insertion code probably looks something like this:

	atomic_inc(&obj->ref_count);
	list_add(&obj->list, &global_obj_list);

And searches look something like:

	for_each(obj, &global_obj_list) {
		if (key_compare(obj->key, key)) {
			atomic_inc(&obj->ref_count);
			return obj;
		}
	}
	return NULL;

Given the above scheme, it must be the case that the list_del()
be visible to other processors before the atomic counter decrement
is performed.  Otherwise, the counter could fall to zero, yet
the object is still visible for lookup on the linked list.  So
we'd get a bogus sequence like this:

	cpu 0				cpu 1
	list_del(&obj->list);
	... visibility delayed ...
					lookup and find obj on
					global_obj_list
	atomic_dec_and_test();
	obj refcount hits zero, this
	is visible globally
					atomic_inc()
					obj refcount incremented
					to one
	list_del() becomes visible

	kfree(obj);
					obj is now freed up memory
					--> CRASH

With the memory barrier semantics required of the atomic_t
operations which return values, the above sequence of memory
visibility can never happen.

We will now cover the atomic bitmask operations.  You will find
that their SMP and memory barrier semantics are similar in shape
to the atomic_t ops above.

Native atomic bit operations are defined to operate on objects
aligned to the size of an "unsigned long" C data type, and are
least of that size.  The endianness of the bits within each
"unsigned long" are the native endianness of the cpu.

	void set_bit(unsigned long nr, volatils unsigned long *addr);
	void clear_bit(unsigned long nr, volatils unsigned long *addr);
	void change_bit(unsigned long nr, volatils unsigned long *addr);

These routines set, clear, and change, respectively, the bit
number indicated by "nr" on the bit mask pointed to by "ADDR".

They must execute atomically, yet there are no implicit memory
barrier semantics required of these interfaces.

	long test_and_set_bit(unsigned long nr, volatils unsigned long *addr);
	long test_and_clear_bit(unsigned long nr, volatils unsigned long *addr);
	long test_and_change_bit(unsigned long nr, volatils unsigned long *addr);

Like the above, except that these routines return a boolean
which indicates whether the changed bit was set _BEFORE_
the atomic bit operation.

These routines, like the atomic_t counter operations returning
values, require explicit memory barrier semantics around their
execution.  All memory operations before the atomic bit operation
call must be made visible globally before the atomic bit operation
is made visible.  Likewise, the atomic bit operation must be
visible globally before any subsequent memory operation is made
visible.  For example:

	obj->dead = 1;
	if (test_and_set_bit(0, &obj->flags))
		/* ... */;
	obj->killed = 1;

The implementation of test_and_set_bit() must guarentee that
"obj->dead = 1;" is visible to cpus before the atomic
memory operation done by test_and_set_bit() becomes visible.
Likewise, the atomic memory operation done by test_and_set_bit()
must become visible before "obj->killed = 1;" is visible.

Finally there is the basic operation:

	long test_bit(unsigned long nr, __const__ volatile unsigned long *addr);

Which returns a boolean indicating if bit "nr" is set in the
bitmask pointed to by "addr".

If explicit memory barriers are required around clear_bit()
(which does not return a value, and thus does not need to
 provide memory barrier semantics), two interfaces are provided:

	void smp_mb__before_clear_bit(void);
	void smp_mb__after_clear_bit(void);

They are used as follows, and are akin to their atomic_t
operation brothers:

	/* All memory operations before this call will
	 * be globally visible before the clear_bit().
	 */
	smp_mb__before_clear_bit();
	clear_bit( ... );

	/* The clear_bit() will be visible before all
	 * subsequent memory operations.
	 */
	 smp_mb__after_clear_bit();

Finally, there are non-atomic versions of the bitmask operations
provided.  They are used in contexts where some other higher-level
SMP locking scheme is being used to protect the bitmask, and
thus less expensive non-atomic operations may be used in the
implementation.  They have names similar to the above bitmask
operation interfaces, except that two underscores are prefixed
to the interface name.

	void __set_bit(unsigned long nr, volatile unsigned long *addr);
	void __clear_bit(unsigned long nr, volatile unsigned long *addr);
	void __change_bit(unsigned long nr, volatile unsigned long *addr);
	long __test_and_set_bit(unsigned long nr, volatile unsigned long *addr);
	long __test_and_clear_bit(unsigned long nr, volatile unsigned long *addr);
	long __test_and_change_bit(unsigned long nr, volatile unsigned long *addr);

These non-atomic variants also do not require any special
memory barrier semantics.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

On Thu, Feb 03, 2005 at 03:08:21PM -0800, David S. Miller wrote:
> 
> Ok, here goes nothing.  Can someone run with this?  It should
> be rather complete, and require only minor editorial work.

Thanks.  It's a very nice piece of work.
 
> A missing memory barrier in the cases where they are required
> by the atomic_t implementation above can have disasterous
> results.  Here is an example, which follows a pattern occuring
> frequently in the Linux kernel.  It is the use of atomic counters
> to implement reference counting, and it works such that once
> the counter falls to zero it can be guarenteed that no other
> entity can be accessing the object.   Observe:
> 
> 	list_del(&obj->list);
> 	if (atomic_dec_and_test(&obj->ref_count))
> 		kfree(obj);
> 
> Here, the list (say it is some linked list on which object
> searches are performed) creates the reference to the object.
> The insertion code probably looks something like this:
> 
> 	atomic_inc(&obj->ref_count);
> 	list_add(&obj->list, &global_obj_list);

I think you should probably note that some sort of locking or RCU
scheme is required to make this safe.  As it is the atomic_inc
and the list_add can be reordered such that the atomic_inc occurs
after the atomic_dec_and_test.

Either that or you can modify the example to add an
smp_mb__after_atomic_inc().  That'd be a good way to
demonstrate its use.

> And searches look something like:
> 
> 	for_each(obj, &global_obj_list) {
> 		if (key_compare(obj->key, key)) {
> 			atomic_inc(&obj->ref_count);
> 			return obj;
> 		}
> 	}
> 	return NULL;

Locking or RCU is definitely needed here.

> the object is still visible for lookup on the linked list.  So
> we'd get a bogus sequence like this:
> 
> 	cpu 0				cpu 1
> 	list_del(&obj->list);
> 	... visibility delayed ...
> 					lookup and find obj on
> 					global_obj_list

The visibility only needs to be delayed up until this point for
the crash to occur.

> 	atomic_dec_and_test();
> 	obj refcount hits zero, this
> 	is visible globally
> 					atomic_inc()
> 					obj refcount incremented
> 					to one
> 	list_del() becomes visible
> 
> 	kfree(obj);
> 					obj is now freed up memory
> 					--> CRASH
> 
> With the memory barrier semantics required of the atomic_t
> operations which return values, the above sequence of memory
> visibility can never happen.

So this isn't exactly correct.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 22:33:05 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> I think you should probably note that some sort of locking or RCU
> scheme is required to make this safe.  As it is the atomic_inc
> and the list_add can be reordered such that the atomic_inc occurs
> after the atomic_dec_and_test.
>
> Either that or you can modify the example to add an
> smp_mb__after_atomic_inc().  That'd be a good way to
> demonstrate its use.

Yeah, this example is totally bogus.  I'll make it match the
neighbour cache case which started this discussion.  Which is
something like:

static void obj_list_add(struct obj *obj)
{
	obj->active = 1;
	list_add(&obj->list);
}

static void obj_list_del(struct obj *obj)
{
	list_del(&obj->list);
	obj->active = 0;
}

static void obj_destroy(struct obj *obj)
{
	BUG_ON(obj->active);
	kfree(obj);
}

struct obj *obj_list_peek(struct list_head *head)
{
	if (!list_empty(head)) {
		struct obj *obj;

		obj = list_entry(head->next, struct obj, list);
		atomic_inc(&obj->refcnt);
		return obj;
	}
	return NULL;
}

void obj_poke(void)
{
	struct obj *obj;

	spin_lock(&global_list_lock);
	obj = obj_list_peek(&global_list);
	spin_unlock(&global_list_lock);

	if (obj) {
		obj->ops->poke(obj);
		if (atomic_dec_and_test(&obj->refcnt))
			obj_destroy(obj);
	}
}

void obj_timeout(struct obj *obj)
{
	spin_lock(&global_list_lock);
	obj_list_del(obj);
	spin_unlock(&global_list_lock);

	if (atomic_dec_and_test(&obj->refcnt))
		obj_destroy(obj);
}

Something like that.  I'll update the atomic_ops.txt
doc and post and updated version later tonight.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Fri, 4 Feb 2005 15:48:55 -0800
"David S. Miller" <davem@davemloft.net> wrote:

> Something like that.  I'll update the atomic_ops.txt
> doc and post and updated version later tonight.

Ok, as promised, here is the updated doc.  Who should
I author this as?  Perhaps "Anton's evil twin" :-)

--- atomic_ops.txt ---

	This document is intended to serve as a guide to Linux port
maintainers on how to implement atomic counter and bitops operations
properly.

	The atomic_t type should be defined as a signed integer.
Also, it should be made opaque such that any kind of cast to
a normal C integer type will fail.  Something like the following
should suffice:

	typedef struct { volatile int counter; } atomic_t;

	The first operations to implement for atomic_t's are
the initializers and plain reads.

	#define ATOMIC_INIT(i)		{ (i) }
	#define atomic_set(v, i)	((v)->counter = (i))

The first macro is used in definitions, such as:

static atomic_t my_counter = ATOMIC_INIT(1);

The second interface can be used at runtime, as in:

	k = kmalloc(sizeof(*k), GFP_KERNEL);
	if (!k)
		return -ENOMEM;
	atomic_set(&k->counter, 0);

Next, we have:

	#define atomic_read(v)	((v)->counter)

which simply reads the current value of the counter.

Now, we move onto the actual atomic operation interfaces.

	void atomic_add(int i, atomic_t *v);
	void atomic_sub(int i, atomic_t *v);
	void atomic_inc(atomic_t *v);
	void atomic_dec(atomic_t *v);

These four routines add and subtract integral values to/from the given
atomic_t value.  The first two routines pass explicit integers by
which to make the adjustment, whereas the latter two use an implicit
adjustment value of "1".

One very important aspect of these two routines is that
they DO NOT require any explicit memory barriers.  They
need only perform the atomic_t counter update in an SMP
safe manner.

Next, we have:

	int atomic_inc_return(atomic_t *v);
	int atomic_dec_return(atomic_t *v);

These routines add 1 and subtract 1, respectively, from
the given atomic_t and return the new counter value after
the operation is performed.

Unlike the above routines, it is required that explicit memory
barriers are performed before and after the operation.  It must
be done such that all memory operations before and after the
atomic operation calls are strongly ordered with respect to the
atomic operation itself.

For example, it should behave as if a smp_mb() call existed both
before and after the atomic operation.

If the atomic instructions used in an implementation provide
explicit memory barrier semantics which satisfy the above requirements,
that is fine as well.

Let's move on:

	int atomic_add_return(int i, atomic_t *v);
	int atomic_sub_return(int i, atomic_t *v);

These behave just like atomic_{inc,dec}_return() except that an
explicit counter adjustment is given instead of the implicit "1".
This means that like atomic_{inc,dec}_return(), the memory barrier
semantics are required.

Next:

	int atomic_inc_and_test(atomic_t *v);
	int atomic_dec_and_test(atomic_t *v);

These two routines increment and decrement by 1, respectively,
the given atomic counter.  They return a boolean indicating
whether the resulting counter value was zero or not.

It requires explicit memory barrier semantics around the operation
as above.

	int atomic_sub_and_test(int i, atomic_t *v);

This is identical to atomic_dec_and_test() except that an explicit
decrement is given instead of the implicit "1".  It requires explicit
memory barrier semantics around the operation.

	int atomic_add_negative(int i, atomic_t *v);

The given increment is added to the given atomic counter value.
A boolean is return which indicates whether the resulting counter
value is negative.  It requires explicit memory barrier semantics
around the operation.

If a caller requires memory barrier semantics around an atomic_t
operation which does not return a value, a set of interfaces
are defined which accomplish this:

	void smb_mb__before_atomic_dec(void);
	void smb_mb__after_atomic_dec(void);
	void smb_mb__before_atomic_inc(void);
	void smb_mb__after_atomic_dec(void);

For example, smb_mb__before_atomic_dec() can be used like so:

	obj->dead = 1;
	smb_mb__before_atomic_dec();
	atomic_dec(&obj->ref_count);

It makes sure that all memory operations preceeding the atomic_dec()
call are strongly ordered with respect to the atomic counter
operation.  In the above example, it guarentees that the assignment
of "1" to obj->dead will be globally visible to other cpus before
the atomic counter decrement.

Without the explicitl smb_mb__before_atomic_dec() call, the
implementation could legally allow the atomic counter update
visible to other cpus before the "obj->dead = 1;" assignment.

The other three interfaces listed are used to provide explicit
ordering with respect to memory operations after an atomic_dec()
call (smb_mb__after_atomic_dec()) and around atomic_inc() calls
(smb_mb__{before,after}_atomic_inc()).

A missing memory barrier in the cases where they are required
by the atomic_t implementation above can have disasterous
results.  Here is an example, which follows a pattern occuring
frequently in the Linux kernel.  It is the use of atomic counters
to implement reference counting, and it works such that once
the counter falls to zero it can be guarenteed that no other
entity can be accessing the object:

static void obj_list_add(struct obj *obj)
{
	obj->active = 1;
	list_add(&obj->list);
}

static void obj_list_del(struct obj *obj)
{
	list_del(&obj->list);
	obj->active = 0;
}

static void obj_destroy(struct obj *obj)
{
	BUG_ON(obj->active);
	kfree(obj);
}

struct obj *obj_list_peek(struct list_head *head)
{
	if (!list_empty(head)) {
		struct obj *obj;

		obj = list_entry(head->next, struct obj, list);
		atomic_inc(&obj->refcnt);
		return obj;
	}
	return NULL;
}

void obj_poke(void)
{
	struct obj *obj;

	spin_lock(&global_list_lock);
	obj = obj_list_peek(&global_list);
	spin_unlock(&global_list_lock);

	if (obj) {
		obj->ops->poke(obj);
		if (atomic_dec_and_test(&obj->refcnt))
			obj_destroy(obj);
	}
}

void obj_timeout(struct obj *obj)
{
	spin_lock(&global_list_lock);
	obj_list_del(obj);
	spin_unlock(&global_list_lock);

	if (atomic_dec_and_test(&obj->refcnt))
		obj_destroy(obj);
}

(This is a simplification of the ARP queue management in the
 generic neighbour discover code of the networking.  Olaf Kirch
 found a bug wrt. memory barriers in kfree_skb() that exposed
 the atomic_t memory barrier requirements quite clearly.)

Given the above scheme, it must be the case that the obj->active
update done by the obj list deletion be visible to other
processors before the atomic counter decrement is performed.

Otherwise, the counter could fall to zero, yet obj->active
would still be set, thus triggering the assertion in
obj_destroy().  The error sequence looks like this:

	cpu 0				cpu 1
	obj_poke()			obj_timeout()
	obj = obj_list_peek();
	... gains ref to obj, refcnt=2
					obj_list_del(obj);
					obj->active = 0 ...
					... visibility delayed ...
					atomic_dec_and_test()
					... refcnt drops to 1 ...
	atomic_dec_and_test()
	... refcount drops to 0 ...
	obj_destroy()
	BUG() triggers since obj->active
	still seen as one
					obj->active update visibility occurs

With the memory barrier semantics required of the atomic_t
operations which return values, the above sequence of memory
visibility can never happen.  Specifically, in the above case
the atomic_dec_and_test() counter decrement would not become
globally visible until the obj->active update does.

We will now cover the atomic bitmask operations.  You will find
that their SMP and memory barrier semantics are similar in shape
and scope to the atomic_t ops above.

Native atomic bit operations are defined to operate on objects
aligned to the size of an "unsigned long" C data type, and are
least of that size.  The endianness of the bits within each
"unsigned long" are the native endianness of the cpu.

	void set_bit(unsigned long nr, volatils unsigned long *addr);
	void clear_bit(unsigned long nr, volatils unsigned long *addr);
	void change_bit(unsigned long nr, volatils unsigned long *addr);

These routines set, clear, and change, respectively, the bit
number indicated by "nr" on the bit mask pointed to by "ADDR".

They must execute atomically, yet there are no implicit memory
barrier semantics required of these interfaces.

	long test_and_set_bit(unsigned long nr, volatils unsigned long *addr);
	long test_and_clear_bit(unsigned long nr, volatils unsigned long *addr);
	long test_and_change_bit(unsigned long nr, volatils unsigned long *addr);

Like the above, except that these routines return a boolean
which indicates whether the changed bit was set _BEFORE_
the atomic bit operation.

WARNING! It is incredibly important that the value be a boolean,
ie. "0" or "1".  Do not try to be fancy and save a few instructions by
just returning something like "old_val & mask" because that will not
work.  For one thing, this return value gets truncated to int in many
code paths, so on 64-bit if the bit is set in the upper 32-bits then
testers will never see that.

One great example of where this problem crops up are the thread_info
flag operations.  Routines such as test_and_set_ti_thread_flag()
chop the return value into an int.  There are other places where
things like this occur as well.

These routines, like the atomic_t counter operations returning
values, require explicit memory barrier semantics around their
execution.  All memory operations before the atomic bit operation
call must be made visible globally before the atomic bit operation
is made visible.  Likewise, the atomic bit operation must be
visible globally before any subsequent memory operation is made
visible.  For example:

	obj->dead = 1;
	if (test_and_set_bit(0, &obj->flags))
		/* ... */;
	obj->killed = 1;

The implementation of test_and_set_bit() must guarentee that
"obj->dead = 1;" is visible to cpus before the atomic
memory operation done by test_and_set_bit() becomes visible.
Likewise, the atomic memory operation done by test_and_set_bit()
must become visible before "obj->killed = 1;" is visible.

Finally there is the basic operation:

	long test_bit(unsigned long nr, __const__ volatile unsigned long *addr);

Which returns a boolean indicating if bit "nr" is set in the
bitmask pointed to by "addr".

If explicit memory barriers are required around clear_bit()
(which does not return a value, and thus does not need to
 provide memory barrier semantics), two interfaces are provided:

	void smp_mb__before_clear_bit(void);
	void smp_mb__after_clear_bit(void);

They are used as follows, and are akin to their atomic_t
operation brothers:

	/* All memory operations before this call will
	 * be globally visible before the clear_bit().
	 */
	smp_mb__before_clear_bit();
	clear_bit( ... );

	/* The clear_bit() will be visible before all
	 * subsequent memory operations.
	 */
	 smp_mb__after_clear_bit();

Finally, there are non-atomic versions of the bitmask operations
provided.  They are used in contexts where some other higher-level
SMP locking scheme is being used to protect the bitmask, and
thus less expensive non-atomic operations may be used in the
implementation.  They have names similar to the above bitmask
operation interfaces, except that two underscores are prefixed
to the interface name.

	void __set_bit(unsigned long nr, volatile unsigned long *addr);
	void __clear_bit(unsigned long nr, volatile unsigned long *addr);
	void __change_bit(unsigned long nr, volatile unsigned long *addr);
	long __test_and_set_bit(unsigned long nr, volatile unsigned long *addr);
	long __test_and_clear_bit(unsigned long nr, volatile unsigned long *addr);
	long __test_and_change_bit(unsigned long nr, volatile unsigned long *addr);

These non-atomic variants also do not require any special
memory barrier semantics.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

On Fri, Feb 04, 2005 at 10:24:28PM -0800, David S. Miller wrote:
> 
> Ok, as promised, here is the updated doc.  Who should

Looks good David.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Werner Almesberger]

David S. Miller wrote:
> 	This document is intended to serve as a guide to Linux port
> maintainers on how to implement atomic counter and bitops operations
> properly.

Finally, some light is shed into one of the most arcane areas of
the kernel ;-) Thanks !

> Unlike the above routines, it is required that explicit memory
> barriers are performed before and after the operation.  It must
> be done such that all memory operations before and after the
> atomic operation calls are strongly ordered with respect to the
> atomic operation itself.

Hmm, given that this description will not only be read by implementers
of atomic functions, but also by users, the "explicit memory barriers"
may be confusing. Who does them, the atomic_* function, or the user ?
In fact, I would call them "implicit", because they're hidden in the
atomic_foo functions :-)

> 	void smb_mb__before_atomic_dec(void);
> 	void smb_mb__after_atomic_dec(void);
> 	void smb_mb__before_atomic_inc(void);
> 	void smb_mb__after_atomic_dec(void);

s/smb_/smp/ :-)

Do they also work for atomic_add and atomic_sub, or do we have to
fall back to smb_mb or atomic_add_return (see below) there ?

> With the memory barrier semantics required of the atomic_t
> operations which return values, the above sequence of memory
> visibility can never happen.

What happens if the operation could return a value, but the user
ignores it ? E.g. if I don't like smp_mb__*, could I just use

	atomic_inc_and_test(foo);

instead of

	smp_mb__before_atomic_inc();
	atomic_inc(foo);
	smp_mb__after_atomic_dec();

? If yes, is this a good idea ?

> These routines, like the atomic_t counter operations returning
> values, require explicit memory barrier semantics around their
> execution.

Very confusing: the barriers aren't around the routines (that
is something the user would be doing), but around whatever does
the atomic stuff inside them.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Herbert Xu]

On Thu, Feb 10, 2005 at 01:23:04AM -0300, Werner Almesberger wrote:
> 
> What happens if the operation could return a value, but the user
> ignores it ? E.g. if I don't like smp_mb__*, could I just use
> 
> 	atomic_inc_and_test(foo);
> 
> instead of
> 
> 	smp_mb__before_atomic_inc();
> 	atomic_inc(foo);
> 	smp_mb__after_atomic_dec();

Yes you can.

> ? If yes, is this a good idea ?

Dave mentioned that on sparc64, atomic_inc_and_test is much more
expensive than the second variant.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Thu, 10 Feb 2005 15:56:47 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> > ? If yes, is this a good idea ?
> 
> Dave mentioned that on sparc64, atomic_inc_and_test is much more
> expensive than the second variant.

Actually, besides the memory barriers themselves, all variants
are equally expensive.

On old i386 chips, the test variants are indeed more expensive.
Linus told me this and there is a note about this in the
atomic_ops.txt file if you look at the current copy :-)

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[David S. Miller]

On Thu, 10 Feb 2005 01:23:04 -0300
Werner Almesberger <wa@almesberger.net> wrote:

> David S. Miller wrote:
> > Unlike the above routines, it is required that explicit memory
> > barriers are performed before and after the operation.  It must
> > be done such that all memory operations before and after the
> > atomic operation calls are strongly ordered with respect to the
> > atomic operation itself.
> 
> Hmm, given that this description will not only be read by implementers
> of atomic functions, but also by users, the "explicit memory barriers"
> may be confusing.

Absolutely, I agree.  My fingers even itched as I typed those lines
in.  I didn't change the wording because I couldn't come up with
anything better.

> In fact, I would call them "implicit", because they're hidden in the
> atomic_foo functions :-)

That's confusing to the implementer :-)

> s/smb_/smp/ :-)

Good catch, fixed in my local copy.

> Do they also work for atomic_add and atomic_sub, or do we have to
> fall back to smb_mb or atomic_add_return (see below) there ?

Macros for the other routines don't exist simply because nobody
ever had a use for them.

In practice they will just work.

> What happens if the operation could return a value, but the user
> ignores it ? E.g. if I don't like smp_mb__*, could I just use
> 
> 	atomic_inc_and_test(foo);

You still get the memory barrier, whether you read the return
value or not.

> > These routines, like the atomic_t counter operations returning
> > values, require explicit memory barrier semantics around their
> > execution.
> 
> Very confusing: the barriers aren't around the routines (that
> is something the user would be doing), but around whatever does
> the atomic stuff inside them.

Yeah, it's the whole implicit/explicit wording issue discussed
above.

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Werner Almesberger]

David S. Miller wrote:
> Absolutely, I agree.  My fingers even itched as I typed those lines
> in.  I didn't change the wording because I couldn't come up with
> anything better.

How about something like:

  Unlike the above routines, atomic_???_return are required to perform
  memory barriers [...]

I think "implicit" and "explicit" here are just confusing, because
you don't define them, and there's no intuitively correct meaning
either.

Perhaps a little warning could also be useful for the reader who
wasn't paying close attention to whose role is described:

  Note: this means that a caller of atomic_add, etc., who needs a
  memory barrier before or after that call has to code the memory
  barrier explicitly, whereas a caller of atomic_???_return can rely
  on said functions to provide the barrier without further ado. For
  the implementor of the atomic functions, the roles are reversed.

> You still get the memory barrier, whether you read the return
> value or not.

That might be something worth mentioning. Not that a construct
is used that gcc can optimize away when nobody cares about the
return value.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/

Re: [PATCH] arp_queue: serializing unlink + kfree_skb

[Dmitry Torokhov]

On Thursday 10 February 2005 22:50, David S. Miller wrote:
> > > Unlike the above routines, it is required that explicit memory
> > > barriers are performed before and after the operation.  It must
> > > be done such that all memory operations before and after the
> > > atomic operation calls are strongly ordered with respect to the
> > > atomic operation itself.
> > 
> > Hmm, given that this description will not only be read by implementers
> > of atomic functions, but also by users, the "explicit memory barriers"
> > may be confusing.
> 
> Absolutely, I agree.  My fingers even itched as I typed those lines
> in.  I didn't change the wording because I couldn't come up with
> anything better.

What about the following:

Unlike the routines above, these functions should always perform memory
barriers before and after the operation in question so that all memory
accesses before and after the atomic operation are strongly ordered with
respect to the atomic operation itself.

-- 
Dmitry