Re: CAS (lws_compare_and_swap32)

Re: CAS (lws_compare_and_swap32)

[Carlos O'Donell]

On Mon, Mar 29, 2010 at 12:13 PM, Carlos O'Donell
<carlos@systemhalted.org> wrote:
> 2010/3/29 NIIBE Yutaka <gniibe@fsij.org>:
>> I am currently investigating FTBFS of gauche (a scheme interpreter) =
on
>> hppa. =A0My knowledge of hppa is quite limited, though. =A0I am not =
on
>> this list. =A0Please send Cc: to me.
>>
>> I have a question of CAS implementation. =A0I assume uni processor
>> system.
>>
>> I am looking at:
>> =A0 =A0 =A0 =A0linux-source-2.6.30/arch/parisc/kernel/syscall.S
>>
>> ----------------
>> =A0 =A0 =A0 =A0/*
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0prev =3D *addr;
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if ( prev =3D=3D old )
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0*addr =3D new;
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return prev;
>> =A0 =A0 =A0 =A0*/
>> [...]
>> cas_action:
>> [...]
>> =A0 =A0 =A0 =A0/* The load and store could fail */
>> 1: =A0 =A0 =A0ldw =A0 =A0 0(%sr3,%r26), %r28
>> =A0 =A0 =A0 =A0sub,<> =A0%r28, %r25, %r0
>> 2: =A0 =A0 =A0stw =A0 =A0 %r24, 0(%sr3,%r26)
>> ----------------
>>
>> Suppose that <addr> points to copy-on-write memory. =A0At the label =
2,
>> storing data to <addr> will invoke memory trap and it will go to
>> do_page_fault() to get new memory. =A0In this scenario, is there a
>> possibility for the process to be scheduled off?
>>
>> Call chain in question is:
>> =A0 =A0 =A0 =A0do_page_fault()
>> =A0 =A0 =A0 =A0 =A0->..-> do_wp_page()
>> =A0 =A0 =A0 =A0 =A0 =A0->..-> __alloc_pages_internal() with GFP_HIGH=
USER_MOVABLE
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0->..> schedule()
>>
>> linux/gfp.h has the definition:
>> #define GFP_HIGHUSER_MOVABLE =A0 =A0(__GFP_WAIT | __GFP_IO | __GFP_F=
S | \
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 __GF=
P_HARDWALL | __GFP_HIGHMEM | \
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 __GF=
P_MOVABLE)
>
> I wrote the LWS CAS implementation.
>
> At the time I wrote it I tried to verify that the process calling the
> CAS could never sleep, since this would make it non-atomic.
>
> There are checks in entry.S to prevent return code-paths from
> scheduling or delivering signals if the process was executing on the
> gateway page.
>
> If we are certain that the above could happen, then a possible soluti=
on is:
> * Enable locks for SMP and UP.
> * If lock is taken for your addresss, return to userspace with EAGAIN=
=2E
> * Userspace yields on EAGAIN and then tries again (we can't use
> FUTEX_WAIT/FUTEX_WAKE on a global process unique variable because LWS
> CAS is expected to work on shmem).
>
> Do we really think the above can happen?

I have CC'd the linux-parisc kernel list.

Kyle,

Do you think the above scenario is possible?

When trying to LWS CAS on a page that is COW, the copy process could
sleep, and thus CAS is non-atomic.

What do you think about the solution I propose?

Cheers,
Carlos.
--
To unsubscribe from this list: send the line "unsubscribe linux-parisc"=
 in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: CAS (lws_compare_and_swap32)

[Kyle McMartin]

On Mon, Mar 29, 2010 at 03:31:55PM -0400, Carlos O'Donell wrote:
>

Can you bounce me the whole thread, please?

regards, Kyle

Re: CAS (lws_compare_and_swap32)

[Carlos O'Donell]

On Mon, Mar 29, 2010 at 4:07 PM, Kyle McMartin <kyle@mcmartin.ca> wrote:
> Can you bounce me the whole thread, please?

You saw the whole thread :-)

Niibe-san has pointed out that if you call LWS CAS on an address of a
shared page, that the COW process may call schedule and sleep, leaving
a small window for a race condition.

On SMP I don't think there is a problem:
* Thread A takes kernel LWS CAS lock.
* Thread A writes to CAS address causing COW
* Thread A sleeps.
* Thread B tries to take kernel LWS CAS lock, fails, returns EAGAIN to
userspace.
* Thread A eventually completes releasing kernel LWS CAS lock.
* Thread B finally takes kernel LWS CAS lock and carries out CAS operation.

Even though Thread A sleeps, there is no way to send it a signal at
this point. All signal delivery is initiated only via PA assembly in
entry.S/syscall.S and that avoids delivering a signal (do_signal, and
do_notify_resume not called) if execution is on the gateway page.

On UP you have a problem:
* Thread A enters LWS CAS (no lock on UP)
* Thread A writes to CAS address causing COW
* Thread A sleeps.
* Thread A completes COW, but finishes time slice before the write is restarted.
* Thread B enters LWS CAS (no lock on UP)
* Thread B writes to CAS address, and finishes time slice.
* Thread A writes to CAS address and clobbers B's value.

The solution is to add the locks to the UP case to avoid this problem.

Cheers,
Carlos.

Re: CAS (lws_compare_and_swap32)

[Kyle McMartin]

On Tue, Mar 30, 2010 at 04:38:08PM -0400, Carlos O'Donell wrote:
> * Thread A enters LWS CAS (no lock on UP)
> * Thread A writes to CAS address causing COW
> * Thread A sleeps.
> * Thread A completes COW, but finishes time slice before the write is restarted.
> * Thread B enters LWS CAS (no lock on UP)
> * Thread B writes to CAS address, and finishes time slice.
> * Thread A writes to CAS address and clobbers B's value.
> 
> The solution is to add the locks to the UP case to avoid this problem.
> 

Yes, removing the CONFIG_SMP on that bit looks like it will solve the
problem.

regards, Kyle

Re: CAS (lws_compare_and_swap32)

[NIIBE Yutaka]

Hi all, thanks for your attention.

Carlos O'Donell wrote:
> On UP you have a problem:
> * Thread A enters LWS CAS (no lock on UP)
> * Thread A writes to CAS address causing COW
> * Thread A sleeps.
> * Thread A completes COW, but finishes time slice before the write is restarted.
> * Thread B enters LWS CAS (no lock on UP)
> * Thread B writes to CAS address, and finishes time slice.
> * Thread A writes to CAS address and clobbers B's value.

I thought like that:
(condition like a young process, or a process after fork
which occurs COW)
* Thread A enters LWS CAS (no lock on UP)
* Thread A writes to CAS address causing COW
* Thread A sleeps for new memory.
  Kernel process scheduling:
    Thread A sleeps
    -> swapper wakes up and got new memory, then sleep
    -> Thread B wakes up
* Thread B enters LWS CAS (no lock on UP)
* Thread B writes to CAS address, causing COW, this time we have memory.
  Writes completes, and finishes time slice.
  Kernel process scheduling like that:
    Thread B sleeps -> Thread A wakes up
* Thread A writes to CAS address and clobbers B's value.

Today, I have a next question.  Is there any cache alias problem here?
Should we invalidate the cache line before "load" and flush the cache
line after "store"?

I am testing on paer.debian.org.  It says D-cache is wribe back,
and that's my concern.

--------------------------
Welcome to paer.debian.org, the Debian hppa porterbox

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Last login: Wed Mar 31 02:31:27 2010 from 150.82.175.29
gniibe@paer:~$ cat /proc/cpuinfo
processor	: 0
cpu family	: PA-RISC 2.0
cpu		: PA8700 (PCX-W2)
cpu MHz		: 750.000000
capabilities	: os64
model		: 9000/800/A500-7X
model name	: Crescendo 750 W2
hversion	: 0x00005e30
sversion	: 0x00000491
I-cache		: 768 KB
D-cache		: 1536 KB (WB, direct mapped)
ITLB entries	: 240
DTLB entries	: 240 - shared with ITLB
bogomips	: 1495.04
software id	: 822930640

--------------------------
-- 

Re: CAS (lws_compare_and_swap32)

[NIIBE Yutaka]

NIIBE Yutaka wrote:
> Today, I have a next question.  Is there any cache alias problem here?
> Should we invalidate the cache line before "load" and flush the cache
> line after "store"?

Sorry, I was confused.  We are talking threads which shares memory
context (space identifier), so, my concern is not relevant.
-- 

Re: CAS (lws_compare_and_swap32)

[John David Anglin]

On Mon, 29 Mar 2010, Carlos O'Donell wrote:

> >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0prev =3D *addr;
> >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if ( prev =3D=3D old )
> >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0*addr =3D new;
> >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return prev;
> >> =A0 =A0 =A0 =A0*/
> >> [...]
> >> cas_action:
> >> [...]
> >> =A0 =A0 =A0 =A0/* The load and store could fail */
> >> 1: =A0 =A0 =A0ldw =A0 =A0 0(%sr3,%r26), %r28
> >> =A0 =A0 =A0 =A0sub,<> =A0%r28, %r25, %r0
> >> 2: =A0 =A0 =A0stw =A0 =A0 %r24, 0(%sr3,%r26)
> >> ----------------
> >>
> >> Suppose that <addr> points to copy-on-write memory. =A0At the labe=
l 2,
> >> storing data to <addr> will invoke memory trap and it will go to
> >> do_page_fault() to get new memory. =A0In this scenario, is there a
> >> possibility for the process to be scheduled off?

> > At the time I wrote it I tried to verify that the process calling t=
he
> > CAS could never sleep, since this would make it non-atomic.
> >
> > There are checks in entry.S to prevent return code-paths from
> > scheduling or delivering signals if the process was executing on th=
e
> > gateway page.
> >
> > If we are certain that the above could happen, then a possible solu=
tion is:
> > * Enable locks for SMP and UP.
> > * If lock is taken for your addresss, return to userspace with EAGA=
IN.
> > * Userspace yields on EAGAIN and then tries again (we can't use
> > FUTEX_WAIT/FUTEX_WAKE on a global process unique variable because L=
WS
> > CAS is expected to work on shmem).

I think the solution may be to proceed the CAS sequence with a probe,w
instruction.  This will trigger a non-access TLB miss fault/non-access
data page fault if its going to happen.  There is a FIXME for case 17
in handle_interruption about this.

Dave
--=20
J. David Anglin                                  dave.anglin@nrc-cnrc.g=
c.ca
National Research Council of Canada              (613) 990-0752 (FAX: 9=
52-6602)
--
To unsubscribe from this list: send the line "unsubscribe linux-parisc"=
 in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: CAS (lws_compare_and_swap32)

[Carlos O'Donell]

On Mon, Mar 29, 2010 at 9:54 PM, John David Anglin
<dave@hiauly1.hia.nrc.ca> wrote:
> I think the solution may be to proceed the CAS sequence with a probe,=
w
> instruction. =A0This will trigger a non-access TLB miss fault/non-acc=
ess
> data page fault if its going to happen. =A0There is a FIXME for case =
17
> in handle_interruption about this.

Then what though? One process has to write to the page to initiate the
COW. How else are you going to initiate the COW? Once in userspace you
are only allowed to write to the CAS value (one word on a page), and
you *can't* because that would violate the CAS semantics and atomicity
requirements.

The "first" process must take the lock, has to write the result to the
page, has to initiate the COW, has to sleep with the lock held, and
the rest have to spin in userpace waiting for it to complete.

AFAICT the rest of the processes are not be able to stop the "first"
process from finishing the COW, so we make forward progress after the
COW is done and the "first" process resumes and unlocks the LWS CAS
lock (for that address range).

Cheers,
Carlos.
--
To unsubscribe from this list: send the line "unsubscribe linux-parisc"=
 in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html