[Xenomai-core] [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Xenomai-core] [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Dmitry Adamushko]

[-- Attachment #1.1: Type: text/plain, Size: 1291 bytes --]

Hello,

following the recent discussion with Jan, here is a patch that aims at
allowing xnintr_lock/unlock actually do what they were supposed to do in the
first instance.

in the shirq case and smp,

1) xnintr_lock/unlock()

we have to guarantee that any possible access to the shirq handlers' list is
taken inside the lock / unlock() section. To this goal, the shirq->counter's
modification have to be separated with a memory barrier from the mentioned
above access.

so the patch takes care of it.

2) now, (1) works as long as the 2nd part (xnintr_detach() ->
xnintr_irq_detach() -> deletion of the element from the list of shirq
handlers)
also respects the rules. Here, a modification of the list (element deletion)
has to be completed before the shirq->active counter being accessed. But the
deletion takes place inside the xnlock_get/put_irq* section
(xnintr_detach()) which always implies a memory barrier in place.

In case of linux, smp_mb__after_atomic_inc() and smp_mb__before_atomic_dec()
would do the job. But so far, I decided not to add something like
xnarch_memory_barrier__after_atomic_inc() :) , provided that both seem to
end up being either mb() or barrier() at the same time (have to check more
thoroughly) anyway.

Any suggestions?

-- 
Best regards,
Dmitry Adamushko

[-- Attachment #1.2: Type: text/html, Size: 1405 bytes --]

[-- Attachment #2: intr.c-mb.patch --]
[-- Type: text/x-patch, Size: 462 bytes --]

--- xenomai/ksrc/nucleus/intr-old.c	2006-11-12 00:17:56.000000000 +0100
+++ xenomai/ksrc/nucleus/intr.c	2006-11-12 00:22:15.000000000 +0100
@@ -135,12 +135,14 @@ static inline void xnintr_shirq_lock(xni
 {
 #ifdef CONFIG_SMP
 	xnarch_atomic_inc(&shirq->active);
+	xnarch_memory_barrier();
 #endif
 }
 
 static inline void xnintr_shirq_unlock(xnintr_shirq_t *shirq)
 {
 #ifdef CONFIG_SMP
+	xnarch_memory_barrier();
 	xnarch_atomic_dec(&shirq->active);
 #endif
 }

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Jan Kiszka]

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

Dmitry Adamushko wrote:
> ...
> In case of linux, smp_mb__after_atomic_inc() and
> smp_mb__before_atomic_dec()
> would do the job. But so far, I decided not to add something like
> xnarch_memory_barrier__after_atomic_inc() :) , provided that both seem to
> end up being either mb() or barrier() at the same time (have to check more
> thoroughly) anyway.
> 
> Any suggestions?

As we now know that this patch actually solves a real issue on SMP
(tested by Paolo in RTAI's RTDM variant recently), I would say /some/
form of it should quickly go into the branches.

Actually, this kind of locking via reference counter, may it be atomic
or per-cpu, is a generic pattern for many (RCU-like) use cases. We have
it in RTnet (and I guess it's broken there as well, sigh), and I could
imagine to use it more broadly in the future. This means we should think
about a generic interface (to reduce the probability to use it the wrong
way around...). And for such an interface, we will have a need of
efficient memory barriers.

I see two paths now:

A) If we go for atomic_inc/dec with such locking service,
xnarch_memory_barrier__after_atomic_inc & friends will be needed anyway
and could be already introduced now.

B) If we aim at per-cpu counters (complicates things, but SMP clearly
benefits), we may simply merge Dmitry's patch as is.

Any thoughts?

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Dmitry Adamushko]

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

> I see two paths now:
>
> A) If we go for atomic_inc/dec with such locking service,
> xnarch_memory_barrier__after_atomic_inc & friends will be needed anyway
> and could be already introduced now.


Yes, this would be better.



> Any thoughts?


I have already sent once to you the message, but I do it now once more. Just
to give some more stuff to think about (although, nobody seems to be
inetersted in memory-barriers :) and maybe, if I'm wrong, someone will point
it out.

**********************************************************

I just noticed that probably the code is still, at least very theoretically,
not perfectly safe.

let's consider the following scenario:

op1;

lock();
op2;
unlock();

op3;

from the Documentation/memory-barriers.txt follows that the only guarantee
here is that "b = c" is executed inside the lock-unlock section (of course,
that's what locks are up too).

But the funny thing is that non of the ops are ordered in respect to each
other!

iow, e.g. the following sequences are possible :

lock(); op1; op2; op3; lock();
or
lock(); op3; op2; op1; lock();

and moreover, pure lock/unlock (without irq disable/enable) doesn't even
imply a compiler barrier for UP.

[ read starting from the line 1150 in the above mentioned doc ]

And now apply all the said above to xnintr_detach() or even linux's
synchronize_irq(). IOW, spin_unlock() doesn't guarantee we have a mb between
element deletion and checking the active flag :)

Ok, maybe it's just in theory. e.g. lock and unlock for x86 seem to imply a
full memory barrier (and, probably, all the rest systems does the same).
Just look at definitions of mb() and spinlocks() for x86. asm("lock; some
write ops") does the trick in both cases.


Jan
>
>
>
>


-- 
Best regards,
Dmitry Adamushko

[-- Attachment #2: Type: text/html, Size: 2496 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Jan Kiszka]

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

Dmitry Adamushko wrote:
>> I see two paths now:
>>
>> A) If we go for atomic_inc/dec with such locking service,
>> xnarch_memory_barrier__after_atomic_inc & friends will be needed anyway
>> and could be already introduced now.
> 
> 
> Yes, this would be better.
> 
> 
> 
>> Any thoughts?
> 
> 
> I have already sent once to you the message, but I do it now once more.

Ah, I remember. Got lost somehow.

> Just
> to give some more stuff to think about (although, nobody seems to be
> inetersted in memory-barriers :) and maybe, if I'm wrong, someone will
> point
> it out.
> 
> **********************************************************
> 
> I just noticed that probably the code is still, at least very
> theoretically,
> not perfectly safe.
> 
> let's consider the following scenario:
> 
> op1;
> 
> lock();
> op2;
> unlock();
> 
> op3;
> 
> from the Documentation/memory-barriers.txt follows that the only guarantee
> here is that "b = c" is executed inside the lock-unlock section (of course,
> that's what locks are up too).
> 
> But the funny thing is that non of the ops are ordered in respect to each
> other!
> 
> iow, e.g. the following sequences are possible :
> 
> lock(); op1; op2; op3; lock();
> or
> lock(); op3; op2; op1; lock();
> 
> and moreover, pure lock/unlock (without irq disable/enable) doesn't even
> imply a compiler barrier for UP.
> 
> [ read starting from the line 1150 in the above mentioned doc ]
> 
> And now apply all the said above to xnintr_detach() or even linux's
> synchronize_irq(). IOW, spin_unlock() doesn't guarantee we have a mb
> between
> element deletion and checking the active flag :)

Well, I must agree with you that there is a potential issue even in the
Linux code. I can't imagine that there is a real one, because this
should have triggered already on some box, but following the theory it
is possible.

> 
> Ok, maybe it's just in theory. e.g. lock and unlock for x86 seem to imply a
> full memory barrier (and, probably, all the rest systems does the same).
> Just look at definitions of mb() and spinlocks() for x86. asm("lock; some
> write ops") does the trick in both cases.
> 

Well, the essence is likely that we should put a real compiler barrier
in spinunlock so that such /potential/ leaking of post-lock code into
the critical region can be excluded. Shouldn't cost anything, should it?

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Dmitry Adamushko]

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

On 20/11/06, Jan Kiszka <jan.kiszka@domain.hid> wrote:

> > Ok, maybe it's just in theory. e.g. lock and unlock for x86 seem to
> imply a
> > full memory barrier (and, probably, all the rest systems does the same).
>
> > Just look at definitions of mb() and spinlocks() for x86. asm("lock;
> some
> > write ops") does the trick in both cases.
> >
>
> Well, the essence is likely that we should put a real compiler barrier
> in spinunlock so that such /potential/ leaking of post-lock code into
> the critical region can be excluded.


But some CPUs still may reorder write ops. (the ones that have write-op
queues) and a compiler barrier doesn't help here. Moreover, a spinlock (here
I'm referring to the linux one) does seem to include a compiler barrier (any
real memory barrier also implies it).

Think about it : spinlocks act as "one-way permeable barriers" and lesser
(one-side) variants of compiler barriers do not exist (it's from the same
document :) - just barrier().
So if spinlock doesn't imply a compiler barrier by default (+ (one-way where
it's available) CPU memory barrier), it's just broken.

Errr... in fact, xnlock_put() doesn't seem to be safe in this respect.
Although, nobody uses it as is. xnlock_put_irqrestore() seems to be safe
though.

xnlock_get() makes use of atomic_cmpxchg() which is mapped on linux's
cmpxchg() which, in turn, is said to be smp_mb() alike.

Ok, I'm stopping further speculations here... Back to practice, so do we go
for smp_mb__before/after_atomic_* counterparts or live it as is? I guess,
those would be more optimal.


Jan
>
>

-- 
Best regards,
Dmitry Adamushko

[-- Attachment #2: Type: text/html, Size: 2258 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Jan Kiszka]

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

Dmitry Adamushko wrote:
> On 20/11/06, Jan Kiszka <jan.kiszka@domain.hid> wrote:
> 
>> > Ok, maybe it's just in theory. e.g. lock and unlock for x86 seem to
>> imply a
>> > full memory barrier (and, probably, all the rest systems does the
>> same).
>>
>> > Just look at definitions of mb() and spinlocks() for x86. asm("lock;
>> some
>> > write ops") does the trick in both cases.
>> >
>>
>> Well, the essence is likely that we should put a real compiler barrier
>> in spinunlock so that such /potential/ leaking of post-lock code into
>> the critical region can be excluded.
> 
> 
> But some CPUs still may reorder write ops. (the ones that have write-op
> queues) and a compiler barrier doesn't help here. Moreover, a spinlock
> (here
> I'm referring to the linux one) does seem to include a compiler barrier
> (any
> real memory barrier also implies it).
> 
> Think about it : spinlocks act as "one-way permeable barriers" and lesser
> (one-side) variants of compiler barriers do not exist (it's from the same
> document :) - just barrier().
> So if spinlock doesn't imply a compiler barrier by default (+ (one-way
> where
> it's available) CPU memory barrier), it's just broken.

As we learned, spin-unlock comes with a one-way barrier. I was referring
two a full compiler barrier to avoid reordering of post-lock with
in-lock code. Or is it even a memory barrier? I hate this. It confuses me.

Well, I guess it's best to leave xnlocks as they are (when they really
match Linux characteristics) and put the required but missing barrier
for xnintr_synchronize() explicitly into the code. To play save (and as
performance is not important in that path), we can use a memory barrier.

> 
> Errr... in fact, xnlock_put() doesn't seem to be safe in this respect.
> Although, nobody uses it as is. xnlock_put_irqrestore() seems to be safe
> though.
> 
> xnlock_get() makes use of atomic_cmpxchg() which is mapped on linux's
> cmpxchg() which, in turn, is said to be smp_mb() alike.

My whole feeling on the xnlock is not that positive. Maybe it would be
good to go through all "home-made" locking primitives with barriers in
mind and an eye on the Linux implementation.

> 
> Ok, I'm stopping further speculations here... Back to practice, so do we go
> for smp_mb__before/after_atomic_* counterparts or live it as is? I guess,
> those would be more optimal.
> 

As I said, I'm still not sure if we finally need it when we may use
per-cpu counters for efficiency reasons on the long-term. If this will
add code or - even more important - an interface (of the system layer)
that will soon be removed again...

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Dmitry Adamushko]

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

>
> > Think about it : spinlocks act as "one-way permeable barriers" and
> lesser
> > (one-side) variants of compiler barriers do not exist (it's from the
> same
> > document :) - just barrier().
> > So if spinlock doesn't imply a compiler barrier by default (+ (one-way
> > where
> > it's available) CPU memory barrier), it's just broken.
>
> As we learned, spin-unlock comes with a one-way barrier. I was referring
> two a full compiler barrier to avoid reordering of post-lock with
> in-lock code.


There is no one-way "compiler barrier".

Or is it even a memory barrier? I hate this. It confuses me.


(1) "compiler barrier" - prevents a compiler from reordering load/store
operations;

(2) "memory barrier" (real CPU memory barrier) - prevents a CPU from doing
the same.

For the spinlocks to be able to guarantee (at least) a "one-way" barrier,
both (1) and (2) have to be combined to achive that goal.

Now, as I said above (it's according to the memory-barrirers doc), there is
just _no_ one-way compiler barrier. So (1) implies the use of barrier() -
which is a "full" compiler barrier.

Moreover, one may consider a memory barrier (2) as a "stronger" version of
the compiler barrier. IOW, a memory barrier (2) is always used in pair with
the compiler one (1).
Otherwise, one asks a CPU not to do reordering but a compiler still may do
it under the hood.
The other way around is not always true, a compiler barrier can be used
without the memory one.


Well, I guess it's best to leave xnlocks as they are (when they really
> match Linux characteristics) and put the required but missing barrier
> for xnintr_synchronize() explicitly into the code. To play save (and as
> performance is not important in that path), we can use a memory barrier.


Yes, I agree here.

> xnlock_get() makes use of atomic_cmpxchg() which is mapped on linux's
> > cmpxchg() which, in turn, is said to be smp_mb() alike.
>
> My whole feeling on the xnlock is not that positive. Maybe it would be
> good to go through all "home-made" locking primitives with barriers in
> mind and an eye on the Linux implementation.


Ack.



> Ok, I'm stopping further speculations here... Back to practice, so do we
> go
> > for smp_mb__before/after_atomic_* counterparts or live it as is? I
> guess,
> > those would be more optimal.
> >
>
> As I said, I'm still not sure if we finally need it when we may use
> per-cpu counters for efficiency reasons on the long-term. If this will
> add code or - even more important - an interface (of the system layer)
> that will soon be removed again...


So could you reveal your vision of per-cpu counters in this scenario (or
something in linux does use it under similar circumstances.. RCU?) At the
first glance, it doesn't seem to be much better. Although, I haven't
elaborated more thoroughly yet...


Jan
>
>
>
>


-- 
Best regards,
Dmitry Adamushko

[-- Attachment #2: Type: text/html, Size: 4087 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Jan Kiszka]

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

Dmitry Adamushko wrote:
>> Ok, I'm stopping further speculations here... Back to practice, so do we
>> go
>> > for smp_mb__before/after_atomic_* counterparts or live it as is? I
>> guess,
>> > those would be more optimal.
>> >
>>
>> As I said, I'm still not sure if we finally need it when we may use
>> per-cpu counters for efficiency reasons on the long-term. If this will
>> add code or - even more important - an interface (of the system layer)
>> that will soon be removed again...
> 
> 
> So could you reveal your vision of per-cpu counters in this scenario (or
> something in linux does use it under similar circumstances.. RCU?) At the
> first glance, it doesn't seem to be much better. Although, I haven't
> elaborated more thoroughly yet...

I was thinking about some SRCU-like mechanism with clear optimisation
focus on the reader-side. See this article for SRCU:

http://lwn.net/Articles/202847/

Having per-cpu counter would let SMP readers benefit - no need for
atomic ops then.

There is currently some discussion going on about refining the
implementation:

http://www.ussg.iu.edu/hypermail/linux/kernel/0611.2/0227.html

It looks to me that we are in the comfortable situation of being able to
avoid such extensions.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

[Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Jan Kiszka]

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

Dmitry Adamushko wrote:
> Hello,
> 
> following the recent discussion with Jan, here is a patch that aims at
> allowing xnintr_lock/unlock actually do what they were supposed to do in
> the first instance.
> 

[...]

> 
> --- xenomai/ksrc/nucleus/intr-old.c	2006-11-12 00:17:56.000000000 +0100
> +++ xenomai/ksrc/nucleus/intr.c	2006-11-12 00:22:15.000000000 +0100
> @@ -135,12 +135,14 @@ static inline void xnintr_shirq_lock(xni
>  {
>  #ifdef CONFIG_SMP
>  	xnarch_atomic_inc(&shirq->active);
> +	xnarch_memory_barrier();
>  #endif
>  }
>  
>  static inline void xnintr_shirq_unlock(xnintr_shirq_t *shirq)
>  {
>  #ifdef CONFIG_SMP
> +	xnarch_memory_barrier();
>  	xnarch_atomic_dec(&shirq->active);
>  #endif
>  }

As Dmitry and I are still a bit undecided about who to evolve such RCU
locks best but still face this SMP bug in the current code, we are
suggesting now to merge the patch above as-is for 2.3 - before things
get lost for the release.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-core] Re: [patch] memory barriers in intr.c :: xnintr_lock/unlock()

[Philippe Gerum]

On Thu, 2006-12-07 at 00:03 +0100, Jan Kiszka wrote:
> Dmitry Adamushko wrote:
> > Hello,
> > 
> > following the recent discussion with Jan, here is a patch that aims at
> > allowing xnintr_lock/unlock actually do what they were supposed to do in
> > the first instance.
> > 
> 
> [...]
> 
> > 
> > --- xenomai/ksrc/nucleus/intr-old.c	2006-11-12 00:17:56.000000000 +0100
> > +++ xenomai/ksrc/nucleus/intr.c	2006-11-12 00:22:15.000000000 +0100
> > @@ -135,12 +135,14 @@ static inline void xnintr_shirq_lock(xni
> >  {
> >  #ifdef CONFIG_SMP
> >  	xnarch_atomic_inc(&shirq->active);
> > +	xnarch_memory_barrier();
> >  #endif
> >  }
> >  
> >  static inline void xnintr_shirq_unlock(xnintr_shirq_t *shirq)
> >  {
> >  #ifdef CONFIG_SMP
> > +	xnarch_memory_barrier();
> >  	xnarch_atomic_dec(&shirq->active);
> >  #endif
> >  }
> 
> As Dmitry and I are still a bit undecided about who to evolve such RCU
> locks best but still face this SMP bug in the current code, we are
> suggesting now to merge the patch above as-is for 2.3 - before things
> get lost for the release.

Ack. It's in my patch queue. Given the changes, the risk for regression
is zero and the situation could only improve with those, so this is
going to be applied last.

> 
> Jan
> 
> _______________________________________________
> Xenomai-core mailing list
> Xenomai-core@domain.hid
> https://mail.gna.org/listinfo/xenomai-core
-- 
Philippe.