question of lr/cs

[a7866...@gmail.com]

1.How did lr check whether the memory word is locked ? Is it possible to happen that  one hart read dirty data while another hart writing same word ?

2.which cs will success

--hart0--            --hart1--

li a0,1                li a0,1

lr a1,(a0)             …

add a1,a1,2      lr a1,(a0)

     …                   add a1,a1,1

     …                   cs a1,a0

cs a1,a0

[Tommy Murphy]

I presume that you meant "sc" not "cs"?

Don't the descriptions of "reservation set" in the specs address your question?

Microarchitectural details are generally (or always?) outside the scope of the specs though.

[Edwin Sutanto]

your cs needs to check that

Sent from my iPhone

On Nov 19, 2021, at 7:03 AM, a7866...@gmail.com <a7866...@gmail.com> wrote:

1.How did lr check whether the memory word is locked ? Is it possible to happen that  one hart read dirty data while another hart writing same word ?

--
You received this message because you are subscribed to the Google Groups "RISC-V ISA Dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to isa-dev+u...@groups.riscv.org.
To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/78b9097f-c7d7-4745-84e8-cdd62fb75dd1n%40groups.riscv.org.

[Dan Petrisko]

Typically, LR/SC is implemented by piggybacking on top of a coherence system. The basic concept is that only a single core can own a word in M (modified) or E (exclusive) state, so LR will get the word in that state before creating the reservation.

LR doesn't actually check a reservation. Doing an LR creates a reservation for that hart. In your example, both harts will create a reservation. Whichever hart LR is last in the global order (not hart order) will clear the reservation of the first hart and then create its own. An SC for another hart will also clear a reservation.

From there, the SC for a hart will succeed if the LR for that hart was the latest in the global order to create a reservation for that location. So more concretely for example,

LR1, LR2, SC1, SC2 -> both SC fail

LR1, SC1, LR2, SC2 -> both SC succeed

LR1, LR2, SC2, SC1 -> SC1 fail, SC2 succeed

...

-Dan

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/1788399B-204A-4B4D-90AD-35350C78F281%40gmail.com.

[Bill Huffman]

The LR makes a reservation.  But it does not remove any other reservation.  If it does, the implementation is vulnerable to livelock.  If only the SC removes the other reservations, then the removal can be atomic with respect to success.  Even then, care is required that the other reservations are removed only when the SC will otherwise be successful – though certain reasons for failure that will not repeat might still be allowed.

 

For similar reasons, it’s important the an LR does not acquire a cache line in the Exclusive or Modified state.  LR should be happy with a Shared state.  If LR requires Exclusive/Modified, LR/SC sequences are vulnerable to livelock.

 

      Bill

 

From: Dan Petrisko <petr...@cs.washington.edu>
Sent: Friday, November 19, 2021 11:56 AM
To: Edwin Sutanto <esut...@gmail.com>
Cc: a7866...@gmail.com <a7866...@gmail.com>; RISC-V ISA Dev <isa...@groups.riscv.org>
Subject: Re: [isa-dev] question of lr/cs

 

EXTERNAL MAIL

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/CABXpatpNxv6kpEOAkXWGdbR9SD-qyQbJQdQoySLaCUJibNVqyg%40mail.gmail.com.

[Edwin Sutanto]

i don’t have the doc in front me

Sent from my iPhone

On Nov 19, 2021, at 9:13 AM, Bill Huffman <huf...@cadence.com> wrote:



The LR makes a reservation.  But it does not remove any other reservation. 

i thought the doc says an LR will remove other reservation, ie you can’t have more than 1 outstanding / nested

If it does, the implementation is vulnerable to livelock.  If only the SC removes the other reservations, then the removal can be atomic with respect to success.  Even then, care is required that the other reservations are removed only when the SC will otherwise be successful – though certain reasons for failure that will not repeat might still be allowed.

 

For similar reasons, it’s important the an LR does not acquire a cache line in the Exclusive or Modified state.  LR should be happy with a Shared state.  If LR requires Exclusive/Modified, LR/SC sequences are vulnerable to livelock.

 

But the two harts’ software will keep trying if their respective SC fail, regardless you gain  exclusive or non-exc

thus livelock

thanks

Edwin

[Bill Huffman]

 

 

From: Edwin Sutanto <esut...@gmail.com>
Sent: Friday, November 19, 2021 12:34 PM
To: Bill Huffman <huf...@cadence.com>
Cc: Dan Petrisko <petr...@cs.washington.edu>; a7866...@gmail.com <a7866...@gmail.com>; RISC-V ISA Dev <isa...@groups.riscv.org>
Subject: Re: [isa-dev] question of lr/cs

 

EXTERNAL MAIL

i don’t have the doc in front me

Sent from my iPhone

On Nov 19, 2021, at 9:13 AM, Bill Huffman <huf...@cadence.com> wrote:



The LR makes a reservation.  But it does not remove any other reservation. 

 

i thought the doc says an LR will remove other reservation, ie you can’t have more than 1 outstanding / nested

 

I realize we may be making different assumptions.  The LR will remove any other reservation on the same hart.  But not on a different hart.  Any given hart only needs to remember a single reservation.

 

I was assuming the subject was different harts.  You may well have been assuming the subject was the same hart.

If it does, the implementation is vulnerable to livelock.  If only the SC removes the other reservations, then the removal can be atomic with respect to success.  Even then, care is required that the other reservations are removed only when the SC will otherwise be successful – though certain reasons for failure that will not repeat might still be allowed.

 

For similar reasons, it’s important the an LR does not acquire a cache line in the Exclusive or Modified state.  LR should be happy with a Shared state.  If LR requires Exclusive/Modified, LR/SC sequences are vulnerable to livelock.

 

 

But the two harts’ software will keep trying if their respective SC fail, regardless you gain  exclusive or non-exc

thus livelock

 

Yes, avoiding livelock is good.  😊

 

     Bill

[Dan Petrisko]

There are reasons to get LR in an exclusive state, namely minimizing coherence traffic if the common case is low contention. But yes, you could also get LR in S and then upgrade to M on SC. For most implementations, you'll need some kind of hardware backoff to solve the livelock problem regardless. 

-Dan

[Bill Huffman]

Agreed, coherence traffic will be reduced by having LR require an exclusive state – but not really by much.  Where LR/SC traffic from multiple cores to the same lock location is large enough for that to matter, live-lock is an increasingly important issue.

 

I can see how a well-designed hardware back-off might make LR requesting exclusive OK.  I think, though, that at the level the discussion was occurring, the assumption should be that LR must only request shared.  The usual optimizations, such as acquiring exclusive when no other core has the line, would be appropriate.

[Bill Huffman]

It’s been pointed out to me that it’s also possible to have the LR unconditionally acquire an exclusive copy of a line if arriving coherence messages for that line do not take effect for some number of cycles – enough cycles for a conformant sequence to execute the corresponding SC.

 

I’ll back off to saying that if LR removes reservations on other harts or requests an exclusive copy of the cache line, either additional features need to be added, or livelock will become a possibility.

 

      Bill

 

From: Bill Huffman
Sent: Friday, November 19, 2021 2:47 PM
To: Dan Petrisko <petr...@cs.washington.edu>
Cc: Edwin Sutanto <esut...@gmail.com>; a7866...@gmail.com <a7866...@gmail.com>; RISC-V ISA Dev <isa...@groups.riscv.org>
Subject: RE: [isa-dev] question of lr/cs

 

Agreed, coherence traffic will be reduced by having LR require an exclusive state – but not really by much.  Where LR/SC traffic from multiple cores to the same lock location is large enough for that to matter, live-lock is an increasingly important issue.

 

I can see how a well-designed hardware back-off might make LR requesting exclusive OK.  I think, though, that at the level the discussion was occurring, the assumption should be that LR must only request shared.  The usual optimizations, such as acquiring exclusive when no other core has the line, would be appropriate.

 

      Bill

[Dan Petrisko]

>I have more concern about how a hart using LR instruction to recognize the state of memory(shared of exclusive), not livelock.

That is uarch specific, but one simple implementation is that the reservation is tracked at cache line granularity by a separate "reservation register", maintaining address and a valid bit. Upon an invalidation or other coherence / pipeline event, the valid bit is cleared and a subsequent SC will fail. Perhaps of interest: here is a library which composes other atomic instructions exclusively using LR/SC primitives: https://github.com/black-parrot-sdk/perch/blob/master/atomics.S

-Dan

On Fri, Nov 19, 2021 at 5:29 PM a7866...@gmail.com <a7866...@gmail.com> wrote:

I have more concern about how a hart using LR instruction to recognize the state of memory(shared of exclusive), not livelock.

Only guarantee the task that fist used LR, the livelock will be solved.

The specification introduced CAS to implement lock, and use LR/SC instruction constructed an atomic swap instruction. But I think LR/SC could direct implement lock, otherwise the atomic swap instruction constructed by LR/SC hardly to be claimed is atomic.

The "cs" in question actually is sc instruction.It is my carelessness.