RISC-V Soft Atomics

[John Burke]

Hi Everyone,

I've been looking around for the answers to a few questions, but can't find anything, so I'm turning here. I'm looking for something akin to soft floats for the RISC-V atomic extension, essentially, libraries or other software to mimic the atomic instructions in the absence of the supporting hardware in the same fashion that soft float does without floating point hardware.

I guess first of all, is something like this feasible for the atomic extension where we get similar guarantees? For instructions like AMOADD or AMOSWAP, this feels sort of not possible, but for LR/SC sequences I was thinking it may be.

If something like this is already in existence, even for only the LR/SC style of things, where can I find it?

Thanks very much,

John

[Dan Petrisko]

We made this library for BlackParrot configurations which only support LR/SC: https://github.com/black-parrot/black-parrot/blob/master/bp_common/test/src/perch/atomics.S

Best,
Dan

--
You received this message because you are subscribed to the Google Groups "RISC-V SW Dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sw-dev+un...@groups.riscv.org.
To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/c6386a75-f32c-419a-9494-9788f8ef859fn%40groups.riscv.org.

[John Burke]

Thanks Dan!

This is very helpful, but I think I may have worded myself confusingly too. I’m assuming I don’t have the hardware for LR and SC as well. This is where I felt I was sort of getting into the land of infeasibility. Is there anything similar for those instructions? Would I be taking some serious risks if I set aside a few words of memory where a pseudo LR and SC would reference to ensure a reservation wasn’t disrupted by another process or interrupt?

Thanks

John

[Nick Knight]

Hi John,

It sounds to me like you may be asking about purely software solutions to the mutual exclusion problem. If so, I'd suggest taking a look at some of the classic approaches to this problem:

https://en.wikipedia.org/wiki/Mutual_exclusion#Software_solutions

These algorithms are applicable to RISC-V machines even without the A-extension, although out-of-order execution may require careful use of memory barriers.

I admit I've never tried to build/use GNU's libatomic, C's _Atomic, or C++'s std::atomic on a RISC-V machine without the A extension. I'm curious to know if/how it works.

Best,

Nick Knight

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CAABsk8cezTx%2BS%2BSm6PeN2evxqFTtehK_x3-7Tyd_mL3U%2BWGukA%40mail.gmail.com.

[John Burke]

Thanks Nick!

I think this is exactly what I need for the first step! Both you and Dan have given me great info so I think I’m ready to go

Thank you both

John

You received this message because you are subscribed to a topic in the Google Groups "RISC-V SW Dev" group.
To unsubscribe from this topic, visit https://groups.google.com/a/groups.riscv.org/d/topic/sw-dev/mQcKbOHCU8Y/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sw-dev+un...@groups.riscv.org.
To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CABpcLcQgGuzGUfVKzLmsuLQdTDLRtOj7HrCBbw8Zb1ze9atcgg%40mail.gmail.com.

[Andrew Waterman]

On Mon, Mar 1, 2021 at 3:33 PM Nick Knight <nick....@sifive.com> wrote:

Hi John,

It sounds to me like you may be asking about purely software solutions to the mutual exclusion problem. If so, I'd suggest taking a look at some of the classic approaches to this problem:

https://en.wikipedia.org/wiki/Mutual_exclusion#Software_solutions

These algorithms are applicable to RISC-V machines even without the A-extension, although out-of-order execution may require careful use of memory barriers.

I admit I've never tried to build/use GNU's libatomic, C's _Atomic, or C++'s std::atomic on a RISC-V machine without the A extension. I'm curious to know if/how it works.

libatomic ultimately depends on the existence of a word-sized CAS primitive.  The OS can provide that primitive in the form of a syscall (which, on a uniprocessor, only needs to disable preemption--assuming user processes aren't communicating with I/O devices using these primitives).  But RISC-V Linux presupposes A-extension support and so doesn't provide such a syscall.

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

[John Burke]

Thanks Andrew!

[Palmer Dabbelt]

On Mon, 01 Mar 2021 16:17:16 PST (-0800), Andrew Waterman wrote:
> On Mon, Mar 1, 2021 at 3:33 PM Nick Knight <nick....@sifive.com> wrote:
>
>> Hi John,
>>
>> It sounds to me like you may be asking about purely software solutions to
>> the mutual exclusion problem. If so, I'd suggest taking a look at some of
>> the classic approaches to this problem:
>>
>> https://en.wikipedia.org/wiki/Mutual_exclusion#Software_solutions
>>
>> These algorithms are applicable to RISC-V machines even without the
>> A-extension, although out-of-order execution may require careful use of
>> memory barriers.
>>
>> I admit I've never tried to build/use GNU's libatomic, C's _Atomic, or
>> C++'s std::atomic on a RISC-V machine without the A extension. I'm curious
>> to know if/how it works.
>>
>
> libatomic ultimately depends on the existence of a word-sized CAS
> primitive. The OS can provide that primitive in the form of a syscall
> (which, on a uniprocessor, only needs to disable preemption--assuming user
> processes aren't communicating with I/O devices using these primitives).
> But RISC-V Linux presupposes A-extension support and so doesn't provide
> such a syscall.

There's a better scheme for supporting atomics on non-A single-hart systems:
only provide trivially restartable atomics, speculate they will succeed, and
restart them on interrupts. A scheme along these lines is implemented in the
ARMv7 Linux port, where a cmpxchg routine is provided by the VDSO with the trap
code restarting from the beginning of that routine whenever it finds itself in
the middle of it. This requires no extra privilege transitions, and has an
efficient ABI-compatible implementation on with-A systems (the scheduler
doesn't check, and the VDSO uses LR/SC).

This is the core of why we tossed the cmpxchg syscall during the glibc
upstreaming process. I wouldn't be opposed to taking the code (and adding the
ABI), but I don't care enough to do it myself.

>>>>> <https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/c6386a75-f32c-419a-9494-9788f8ef859fn%40groups.riscv.org?utm_medium=email&utm_source=footer>
>>>>> .

>>>>>
>>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "RISC-V SW Dev" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an
>>> email to sw-dev+un...@groups.riscv.org.
>>> To view this discussion on the web visit

>>> https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CAABsk8cezTx%2BS%2BSm6PeN2evxqFTtehK_x3-7Tyd_mL3U%2BWGukA%40mail.gmail.com
>>> <https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CAABsk8cezTx%2BS%2BSm6PeN2evxqFTtehK_x3-7Tyd_mL3U%2BWGukA%40mail.gmail.com?utm_medium=email&utm_source=footer>
>>> .

>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "RISC-V SW Dev" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to sw-dev+un...@groups.riscv.org.
>> To view this discussion on the web visit

>> https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CABpcLcQgGuzGUfVKzLmsuLQdTDLRtOj7HrCBbw8Zb1ze9atcgg%40mail.gmail.com
>> <https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CABpcLcQgGuzGUfVKzLmsuLQdTDLRtOj7HrCBbw8Zb1ze9atcgg%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .

>>
>
> --
> You received this message because you are subscribed to the Google Groups "RISC-V SW Dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sw-dev+un...@groups.riscv.org.

> To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CA%2B%2B6G0BRGPv%2Bxpkjy%3D1srAKM%2B4Bw8dFHbXcXy9p7%2BukiKZDF5Q%40mail.gmail.com.

[Andrew Waterman]

Yep, that's a much more performant approach.

This is the core of why we tossed the cmpxchg syscall during the glibc
upstreaming process.  I wouldn't be opposed to taking the code (and adding the
ABI), but I don't care enough to do it myself.

Is the rest of the kernel in reasonable shape for omitting the A extension (for non-SMP, I mean)?  I mean, do you think the vDSO cmpxchg scheme represents the bulk of the necessary work?

[Andrew Waterman]

On Tue, Mar 2, 2021 at 6:19 PM <ge...@mailworks.org> wrote:

It appears possible to support SMP soft atomics, albeit slowly, given a fixed known number of harts in the constrained case where all atomic ops only ever compete with other atomic ops, and not with normal stores.  What's less clear is the likelihood that all software of interest adheres to that restriction, as does the mutual exclusion example code in the A extension chapter of the specs.  Perhaps if this is a common enough use pattern, the A chapter's non-normative comment about using the AMO Swap idiom instead of a store can also mention the value of a generalized and consistent use of this approach (avoiding race conditions between stores and atomic ops) for SMP soft atomics.

Assuming also of course that the reasoning holds and this actually works.  And without implying SMP soft atomics are particularly practical.

Luckily, I think such a system is mostly a curiosity--good fodder for exam questions, not so much a problem we need to solve :)

[Observing the list without creating a Google account.  Feel free to reply on the list or not.]

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/CA%2B%2B6G0BKFtM1Bq8zHOfRq5G0H51%3DhhjKhjUseu6ubM0b_QXGnw%40mail.gmail.com.

[ds2h...@gmail.com]

On Tuesday, 2 March 2021 at 21:36:26 UTC-5 andrew wrote:

On Tue, Mar 2, 2021 at 6:19 PM <ge...@mailworks.org> wrote:

It appears possible to support SMP soft atomics, albeit slowly, given a fixed known number of harts in the constrained case where all atomic ops only ever compete with other atomic ops, and not with normal stores.  What's less clear is the likelihood that all software of interest adheres to that restriction, as does the mutual exclusion example code in the A extension chapter of the specs.  Perhaps if this is a common enough use pattern, the A chapter's non-normative comment about using the AMO Swap idiom instead of a store can also mention the value of a generalized and consistent use of this approach (avoiding race conditions between stores and atomic ops) for SMP soft atomics.

Assuming also of course that the reasoning holds and this actually works.  And without implying SMP soft atomics are particularly practical.

Luckily, I think such a system is mostly a curiosity--good fodder for exam questions, not so much a problem we need to solve :)

 

I can see VSDO support being a life saver for a company that ran off thousands of chips that have an errata affecting Atomics.

They can continue to develop and prove the rest of their system with real chips. They have the  possibility to sell them at a discount and still get to market.

If supported it can only help our RISCV.org cause.

I was disappointed when VSDO for RISCV was dropped.

[perhaps even a little bitter because it was the next support area I considered for after my optimization for using SP rather than thread pointer in sscratch, which was rejected back in 2017.

I was dejected enough to not bother submitting anything else. ]

[Andrew Waterman]

On Tue, Mar 2, 2021 at 7:41 PM ds2h...@gmail.com <ds2h...@gmail.com> wrote:

On Tuesday, 2 March 2021 at 21:36:26 UTC-5 andrew wrote:

On Tue, Mar 2, 2021 at 6:19 PM <ge...@mailworks.org> wrote:

It appears possible to support SMP soft atomics, albeit slowly, given a fixed known number of harts in the constrained case where all atomic ops only ever compete with other atomic ops, and not with normal stores.  What's less clear is the likelihood that all software of interest adheres to that restriction, as does the mutual exclusion example code in the A extension chapter of the specs.  Perhaps if this is a common enough use pattern, the A chapter's non-normative comment about using the AMO Swap idiom instead of a store can also mention the value of a generalized and consistent use of this approach (avoiding race conditions between stores and atomic ops) for SMP soft atomics.

Assuming also of course that the reasoning holds and this actually works.  And without implying SMP soft atomics are particularly practical.

Luckily, I think such a system is mostly a curiosity--good fodder for exam questions, not so much a problem we need to solve :)

 

I can see VSDO support being a life saver for a company that ran off thousands of chips that have an errata affecting Atomics.

They can continue to develop and prove the rest of their system with real chips. They have the  possibility to sell them at a discount and still get to market.

If supported it can only help our RISCV.org cause.

I was disappointed when VSDO for RISCV was dropped.

It wasn't meant to be an irrevocable decision, of course.  If there's sufficient demand, the Linux and toolchain developers will eventually create an alternate ABI that relies upon vDSO calls for CAS.  (For single-hart systems, anyway.)  I'm skeptical, but I'm certainly not in any position to oppose it.

[James Y Knight]

It's always seemed quite unfortunate that the LR/SC instructions aren't in the baseline RISCV ISA -- or at the very least, implemented in practice by every CPU that matters. They're trivial to implement in a single-hart CPU design using a single bit of state ("is an LR currently outstanding"), and it'd make software a whole lot simpler to be able to be able to simply depend on their presence...

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/sw-dev/mhng-ebe04d30-25ab-42fc-9ba7-1de6d5de3a9f%40palmerdabbelt-glaptop.

[Maciej W. Rozycki]

On Wed, 3 Mar 2021, 'James Y Knight' via RISC-V SW Dev wrote:

> It's always seemed quite unfortunate that the LR/SC instructions aren't in
> the baseline RISCV ISA -- or at the very least, implemented in practice by
> every CPU that matters. They're trivial to implement in a single-hart CPU
> design using a single bit of state ("is an LR currently outstanding"), and
> it'd make software a whole lot simpler to be able to be able to simply
> depend on their presence...

You can always trap and emulate that stuff on UP, just as we chose for
MIPS I implementations at one point. This way all software remains
compatible with all hardware, performs optimally on good hardware and
performs at all on crippled hardware.

I agree it seems rather embarassing to me to repeat the MIPS base ISA's
mistake back from 1985: MIPS I CPU implementations such as the original
R3000 did support the hardware protocols required for MP operation and
just missed software provisions for atomics which weren't defined in the
ISA, and actual MP systems such as the DECsystem 5800 were manufactured
and sold having external solutions like gating storage built into board
logic for mutex support.

FWIW,

Maciej