RE: atomic operations in user space

RE: atomic operations in user space

[Liu Dave-r63238]

[snip]
> I surely know all the theories you mentioned clearly.  But=20
> please do look at the case I gave.  Correct me if I missed=20
> anything.  Thanks
>=20
> All the lwarx and stwcx operate on the same address.
>=20
> > Task A		Task B
> > lwarx			=09
> // Get RESERVATION
> > 			......
> > 			lwarx
> > 			stwcx
>=20
> // RESERVATION cleared
> >
> > 			.....
> > 			.....
> > 			lwarx
>=20
> // Get RESERVATION again
> > stwcx			=09
>=20
> //Note here: RESERVATION is valid, address is the same.
> So the result is commited, no retry for task A
>=20
> > .....
> > 			stwcx
> //RESERVATION is cleared, retry atomic op for task B
>=20
> Please be noted that reservation is only identified by=20
> reservation bit and address operated on.  So different=20
> lwarx's on the same address, may be considered as the same=20
> reservation.

Is this your reason we cannot do atomic operation in user space?

How about the kernel space? You can image it.
The context switching as above also happen in kernel space,
Why we can do atomic operation in kernel space, not do in user space?

You are assuming the context switching cause the reservation broken.
but we can do atomic operation in kernel space.  The context switching
really is the execption of processor, If we can clear the wrong
RESERVATION
before exception return, I think we can solve this problem. We can dummy
stwcx. before exception return or the processor automaticly clear the
reservation in exception.=20

Are you missing these important things?

-DAve

RE: atomic operations in user space

[Liu Dave-r63238]

> [snip]
> > I surely know all the theories you mentioned clearly.  But=20
> please do=20
> > look at the case I gave.  Correct me if I missed anything.  Thanks
> >=20
> > All the lwarx and stwcx operate on the same address.
> >=20
> > > Task A		Task B
> > > lwarx			=09
> > // Get RESERVATION
> > > 			......
> > > 			lwarx
> > > 			stwcx
> >=20
> > // RESERVATION cleared
> > >
> > > 			.....
> > > 			.....
> > > 			lwarx
> >=20
> > // Get RESERVATION again
> > > stwcx			=09
> >=20
> > //Note here: RESERVATION is valid, address is the same.
> > So the result is commited, no retry for task A
> >=20
> > > .....
> > > 			stwcx
> > //RESERVATION is cleared, retry atomic op for task B
> >=20
> > Please be noted that reservation is only identified by=20
> reservation bit=20
> > and address operated on.  So different lwarx's on the same address,=20
> > may be considered as the same reservation.
>=20
> Is this your reason we cannot do atomic operation in user space?
>=20
> How about the kernel space? You can image it.
> The context switching as above also happen in kernel space,=20
> Why we can do atomic operation in kernel space, not do in user space?
>=20
> You are assuming the context switching cause the reservation broken.
> but we can do atomic operation in kernel space.  The context=20
> switching really is the execption of processor, If we can=20
> clear the wrong RESERVATION before exception return, I think=20
> we can solve this problem. We can dummy stwcx. before=20
> exception return or the processor automaticly clear the=20
> reservation in exception.=20
>=20
> Are you missing these important things?
>=20
> -DAve

I got it. I noticed that all of execption return in kernel did stwcx.
to clear the wrong reserved bit. See the source code.

        .globl  ret_from_except_full
ret_from_except_full:
        REST_NVGPRS(r1)
        /* fall through */

        .globl  ret_from_except
ret_from_except:
           ......

restore:
        lwz     r0,GPR0(r1)
        lwz     r2,GPR2(r1)
        REST_4GPRS(3, r1)
        REST_2GPRS(7, r1)

        lwz     r10,_XER(r1)
        lwz     r11,_CTR(r1)
        mtspr   SPRN_XER,r10
        mtctr   r11

        PPC405_ERR77(0,r1)
        stwcx.  r0,0,r1                 /* to clear the reservation */

          ......

         rfi

-DAve

 =20

RE: atomic operations in user space

[Li Yang-r58472]

> -----Original Message-----
> From: Liu Dave-r63238
> Sent: Wednesday, August 30, 2006 10:27 AM
> To: Liu Dave-r63238; Li Yang-r58472; linuxppc-embedded@ozlabs.org;
> linuxppc-dev@ozlabs.org
> Subject: RE: atomic operations in user space
>=20
> > [snip]
> > > I surely know all the theories you mentioned clearly.  But
> > please do
> > > look at the case I gave.  Correct me if I missed anything.  Thanks
> > >
> > > All the lwarx and stwcx operate on the same address.
> > >
> > > > Task A		Task B
> > > > lwarx
> > > // Get RESERVATION
> > > > 			......
> > > > 			lwarx
> > > > 			stwcx
> > >
> > > // RESERVATION cleared
> > > >
> > > > 			.....
> > > > 			.....
> > > > 			lwarx
> > >
> > > // Get RESERVATION again
> > > > stwcx
> > >
> > > //Note here: RESERVATION is valid, address is the same.
> > > So the result is commited, no retry for task A
> > >
> > > > .....
> > > > 			stwcx
> > > //RESERVATION is cleared, retry atomic op for task B
> > >
> > > Please be noted that reservation is only identified by
> > reservation bit
> > > and address operated on.  So different lwarx's on the same
address,
> > > may be considered as the same reservation.
> >
> > Is this your reason we cannot do atomic operation in user space?
> >
> > How about the kernel space? You can image it.
> > The context switching as above also happen in kernel space,
> > Why we can do atomic operation in kernel space, not do in user
space?
> >
> > You are assuming the context switching cause the reservation broken.
> > but we can do atomic operation in kernel space.  The context
> > switching really is the execption of processor, If we can
> > clear the wrong RESERVATION before exception return, I think
> > we can solve this problem. We can dummy stwcx. before
> > exception return or the processor automaticly clear the
> > reservation in exception.
> >
> > Are you missing these important things?
> >
> > -DAve
>=20
> I got it. I noticed that all of execption return in kernel did stwcx.
> to clear the wrong reserved bit. See the source code.
>=20
>         .globl  ret_from_except_full
> ret_from_except_full:
>         REST_NVGPRS(r1)
>         /* fall through */
>=20
>         .globl  ret_from_except
> ret_from_except:
>            ......
>=20
> restore:
>         lwz     r0,GPR0(r1)
>         lwz     r2,GPR2(r1)
>         REST_4GPRS(3, r1)
>         REST_2GPRS(7, r1)
>=20
>         lwz     r10,_XER(r1)
>         lwz     r11,_CTR(r1)
>         mtspr   SPRN_XER,r10
>         mtctr   r11
>=20
>         PPC405_ERR77(0,r1)
>         stwcx.  r0,0,r1                 /* to clear the reservation */

Ya, you found the point.  There is no problem for me about this
question.

- Leo

RE: RE: atomic operations in user space

[Li Yang-r58472]

> -----Original Message-----
> From: Liu Dave-r63238
> Sent: Wednesday, August 30, 2006 10:17 AM
> To: Li Yang-r58472; linuxppc-embedded@ozlabs.org;
linuxppc-dev@ozlabs.org
> Subject: RE: atomic operations in user space
>=20
> [snip]
> > I surely know all the theories you mentioned clearly.  But
> > please do look at the case I gave.  Correct me if I missed
> > anything.  Thanks
> >
> > All the lwarx and stwcx operate on the same address.
> >
> > > Task A		Task B
> > > lwarx
> > // Get RESERVATION
> > > 			......
> > > 			lwarx
> > > 			stwcx
> >
> > // RESERVATION cleared
> > >
> > > 			.....
> > > 			.....
> > > 			lwarx
> >
> > // Get RESERVATION again
> > > stwcx
> >
> > //Note here: RESERVATION is valid, address is the same.
> > So the result is commited, no retry for task A
> >
> > > .....
> > > 			stwcx
> > //RESERVATION is cleared, retry atomic op for task B
> >
> > Please be noted that reservation is only identified by
> > reservation bit and address operated on.  So different
> > lwarx's on the same address, may be considered as the same
> > reservation.
>=20
> Is this your reason we cannot do atomic operation in user space?
>=20
> How about the kernel space? You can image it.
> The context switching as above also happen in kernel space,
> Why we can do atomic operation in kernel space, not do in user space?
>

There are substantial different between kernel and user control path.
First, interrupt can't be interrupted by user process.  Second, context
switch can be explicitly controlled in kernel, but not in user space.

> You are assuming the context switching cause the reservation broken.
> but we can do atomic operation in kernel space.  The context switching
> really is the execption of processor, If we can clear the wrong
RESERVATION
> before exception return, I think we can solve this problem. We can
dummy
> stwcx. before exception return or the processor automaticly clear the
> reservation in exception.

I assume stwcx is a costing instruction, and I don't see such code
indeed.

- Leo

RE: RE: atomic operations in user space

[Liu Dave-r63238]

[snip]
> >=20
> > Is this your reason we cannot do atomic operation in user space?
> >=20
> > How about the kernel space? You can image it.
> > The context switching as above also happen in kernel space,=20
> Why we can=20
> > do atomic operation in kernel space, not do in user space?
> >
>=20
> There are substantial different between kernel and user=20
> control path.  First, interrupt can't be interrupted by user=20
> process.  Second, context switch can be explicitly controlled=20
> in kernel, but not in user space.

I agree this, but from the processor's view, the context switch
is the same to user space and kernel space. The exception
control flow only happen at exception interrupt.=20

What is different you point ?

> > You are assuming the context switching cause the reservation broken.
> > but we can do atomic operation in kernel space.  The=20
> context switching=20
> > really is the execption of processor, If we can clear the wrong=20
> > RESERVATION before exception return, I think we can solve this=20
> > problem. We can dummy stwcx. before exception return or the=20
> processor=20
> > automaticly clear the reservation in exception.
>=20
> I assume stwcx is a costing instruction, and I don't see such=20
> code indeed.

RE: RE: atomic operations in user space

[Li Yang-r58472]

> -----Original Message-----
> From: Liu Dave-r63238
> Sent: Wednesday, August 30, 2006 10:43 AM
> To: Li Yang-r58472; 'linuxppc-embedded@ozlabs.org';
'linuxppc-dev@ozlabs.org'
> Subject: RE: RE: atomic operations in user space
>=20
> [snip]
> > >
> > > Is this your reason we cannot do atomic operation in user space?
> > >
> > > How about the kernel space? You can image it.
> > > The context switching as above also happen in kernel space,
> > Why we can
> > > do atomic operation in kernel space, not do in user space?
> > >
> >
> > There are substantial different between kernel and user
> > control path.  First, interrupt can't be interrupted by user
> > process.  Second, context switch can be explicitly controlled
> > in kernel, but not in user space.
>=20
> I agree this, but from the processor's view, the context switch
> is the same to user space and kernel space. The exception
> control flow only happen at exception interrupt.

Exception is special and tiny part of the kernel, which should be
programmed carefully not to break any thing.  Anyway, as you found,
clear reservation in exception do solve all the problems.

>=20
> What is different you point ?
>=20
> > > You are assuming the context switching cause the reservation
broken.
> > > but we can do atomic operation in kernel space.  The
> > context switching
> > > really is the execption of processor, If we can clear the wrong
> > > RESERVATION before exception return, I think we can solve this
> > > problem. We can dummy stwcx. before exception return or the
> > processor
> > > automaticly clear the reservation in exception.
> >
> > I assume stwcx is a costing instruction, and I don't see such
> > code indeed.

RE: RE: atomic operations in user space

[Liu Dave-r63238]

> > [snip]
> > > >
> > > > Is this your reason we cannot do atomic operation in user space?
> > > >
> > > > How about the kernel space? You can image it.
> > > > The context switching as above also happen in kernel space,
> > > Why we can
> > > > do atomic operation in kernel space, not do in user space?
> > > >
> > >
> > > There are substantial different between kernel and user control=20
> > > path.  First, interrupt can't be interrupted by user process. =20
> > > Second, context switch can be explicitly controlled in=20
> kernel, but=20
> > > not in user space.
> >=20
> > I agree this, but from the processor's view, the context=20
> switch is the=20
> > same to user space and kernel space. The exception control=20
> flow only=20
> > happen at exception interrupt.
> > What is different you point ?
>=20
> Exception is special and tiny part of the kernel, which=20
> should be programmed carefully not to break any thing. =20
> Anyway, as you found, clear reservation in exception do solve=20
> all the problems.

Can we do atomic operation in user space as kernel space?

> > > > You are assuming the context switching cause the=20
> reservation broken.
> > > > but we can do atomic operation in kernel space.  The
> > > context switching
> > > > really is the execption of processor, If we can clear the wrong=20
> > > > RESERVATION before exception return, I think we can solve this=20
> > > > problem. We can dummy stwcx. before exception return or the
> > > processor
> > > > automaticly clear the reservation in exception.
> > >
> > > I assume stwcx is a costing instruction, and I don't see=20
> such code=20
> > > indeed.

Re: RE: atomic operations in user space

[Olof Johansson]

On Wed, Aug 30, 2006 at 10:55:39AM +0800, Liu Dave-r63238 wrote:

> Can we do atomic operation in user space as kernel space?

Yes.


-Olof

Atomic operations in user space: Yes but No

[Benjamin Herrenschmidt]

On Wed, 2006-08-30 at 01:33 -0500, Olof Johansson wrote:
> On Wed, Aug 30, 2006 at 10:55:39AM +0800, Liu Dave-r63238 wrote:
> 
> > Can we do atomic operation in user space as kernel space?

Ok, let's hope that clarifies it for everybody.

Atomic operations in user space are possible using reservations
(lwarx/stwcx. or their 64 bits counterpart). However they are very much
not recommended.

The reason they work is that the kernel always clears all pending
reservations in the exception path, thus if there is a task switch, an
interrupt or anything that can break the user program flow in the middle
of it's lwarx/stwcx. loop, the kernel will return to userspace with all
reservations cleared, thus causing stwcx. to fail.

However, they are not recommended unless you know VERY WELL what you are
doing. When I say, VERY WELL in all uppercases, I really mean it. That
is examples in books etc... are usually not enough to know very well
what you are doing :) There are three issues at hand at least that I
know about use of lwarx/stwcx, from the less to the most important:

 - Processor erratas. For example, the 405 requires a sync in an atomic
loop. The kernel has a mecanism to have those sync's in and eventually
comment them out at runtime. Future processors might have different
erratas regarding those instructions. It's better to keep their usage
local to the kernel and/or glibc to avoid having to fix too much
userland problems when that happens.

 - Performance issues and possible livelocks. There are both processor
and bus starvation issues related to the use of atomics. On some
processors, it's very recommended for example, when a lock operation
fails, to go do something else for a while (intentional branch
mispredict for example) before trying again. In general, there are
issues with cache lines used for lwarx/stwcx. ping-ponging all over the
fabric on some heavy duty SMP machines if great care isn't taken with
the way atomics or locks are laid out in memory and shared among
threads. 

 - Correctness vs. storage ordering. That's the biggest one. Almost
every time I've seen userland code try to do their own atomic stuffs, it
was done without full understanding of the out of order storage model of
the PowerPC architecture and thus without appropriate barriers. This is
a complicated topic and thus I won't get into a long explanation here,
but let's say that outside of pure atomic "counters" that have no
specific ordering requirements or no locking/exclusion semantics vs. the
execution flow, you should _not_ try to do it yourself with atomics, but
instead use some of the primitives provided by glibc. With NPTL,
nowadays, glibc provides pretty fast implementations that do not use the
kernel unless there is contention.

So yes, you can, but most of the time, you should not.

Cheers,
Ben.