CAS (lws_compare_and_swap32)

DISCUSSION Carlos O'Donell 4 participants 8 messages Mar 29, 2010 – Apr 1, 2010 2 messages not in the archive

lore

Share & tools

lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Carlos O'Donell

author

2010-03-29 19:31 UTC #2 lore raw

Quoted 2 lines · Carlos O'Donell

2010/3/29 NIIBE Yutaka <[email protected]>:
Quoted 1 line
I am currently investigating FTBFS of gauche (a scheme interpreter) =

Quoted 1 line

Quoted 1 line
hppa. =A0My knowledge of hppa is quite limited, though. =A0I am not =

Quoted 24 lines

Quoted 24 lines
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)
----------------

Quoted 1 line

Quoted 1 line
Suppose that <addr> points to copy-on-write memory. =A0At the label =

Quoted 8 lines

Quoted 8 lines
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

Quoted 4 lines

Quoted 4 lines
=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 | \

Quoted 1 line

Quoted 1 line
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 __GF=

P_HARDWALL | __GFP_HIGHMEM | \

Quoted 1 line

Quoted 1 line
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 __GF=

P_MOVABLE)

Quoted 11 lines

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:

Quoted 2 lines

* Enable locks for SMP and UP.
* If lock is taken for your addresss, return to userspace with EAGAIN=

=2E

Quoted 5 lines

* 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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Kyle McMartin

2010-03-29 20:07 UTC #3 lore raw

Quoted 1 line · Carlos O'Donell

Can you bounce me the whole thread, please?

regards, Kyle

Carlos O'Donell

author

2010-03-30 20:38 UTC #4 lore raw

Quoted 1 line · Kyle McMartin

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.

Kyle McMartin

2010-03-30 21:36 UTC #5 lore raw

Quoted 10 lines · Carlos O'Donell

* 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

NIIBE Yutaka

2010-04-01 01:16 UTC #6 lore raw

In reply to Carlos O'Donell

Hi all, thanks for your attention.

Quoted 8 lines · Carlos O'Donell

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

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

NIIBE Yutaka

2010-04-01 01:57 UTC #7 lore raw

Quoted 3 lines · NIIBE Yutaka

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.

John David Anglin

2010-03-30 01:54 UTC #8 lore raw

In reply to Carlos O'Donell

Quoted 14 lines · Carlos O'Donell

Quoted 14 lines
Quoted 14 lines
=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)
----------------

Quoted 1 line

Quoted 1 line
Quoted 1 line
Suppose that <addr> points to copy-on-write memory. =A0At the labe=

l 2,

Quoted 5 lines

Quoted 5 lines
Quoted 3 lines
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=

Quoted 4 lines

Quoted 4 lines
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=

Quoted 3 lines

Quoted 3 lines
gateway page.
If we are certain that the above could happen, then a possible solu=

tion is:

Quoted 2 lines

Quoted 2 lines
* Enable locks for SMP and UP.
* If lock is taken for your addresss, return to userspace with EAGA=

IN.

Quoted 2 lines

Quoted 2 lines
* Userspace yields on EAGAIN and then tries again (we can't use FUTEX_WAIT/FUTEX_WAKE on a global process unique variable because L=

Quoted 1 line

Quoted 1 line
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 [email protected]=
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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Carlos O'Donell

author

2010-03-30 02:18 UTC #9 lore raw

Quoted 1 line · John David Anglin

I think the solution may be to proceed the CAS sequence with a probe,=

Quoted 1 line

instruction. =A0This will trigger a non-access TLB miss fault/non-acc=

ess

Quoted 1 line

data page fault if its going to happen. =A0There is a FIXME for case =

Quoted 1 line

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).