OSDev.org

The Place to Start for Operating System Developers
It is currently Mon Apr 12, 2021 1:16 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Progress guarantees of Arm LL/SC
PostPosted: Thu Jun 01, 2017 9:00 am 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 360
I don't develop for Arm, but wanted to ask anyway.

Generally, code with LDREX and STREX (or LDAXR and STLXR) when properly implemented and supported by the OS is considered lock-free. I mean basic operations, like increments, CAS, etc. Then again, I get the feeling of obstruction-freedom more than lock-freedom from the Arm specs. Like two cores looping tightly over a LL/SC loop might fail STREX due to each other's LDREXs and make no progress for some arbitrary amount of time. May be I am misunderstanding the term "exclusive monitor" here.

So, what are the progress guarantees of a tight LL/SC loop implementing basic operation for Arm compliant CPUs, assuming no interrupts or other memory accesses intervene. Can lock-freedom be achieved, or is it obstruction free code at best?

PS: To rephrase the question. Does a LDREX from a competing core fail the STREX of a core that already holds exclusive monitor on that address?


Top
 Profile  
 
 Post subject: Re: Progress guarantees of Arm LL/SC
PostPosted: Thu Jun 01, 2017 9:57 am 
Offline
Member
Member

Joined: Wed Jan 08, 2014 8:41 am
Posts: 100
Location: Moscow, Russia
My v7-A manual says this at the very end of subsection A3.4.5:
Quote:
In the event of repeatedly-contending load-exclusive/store-exclusive sequences from multiple processors, an implementation must ensure that forward progress is made by at least one processor.


simeonz wrote:
Does a LDREX from a competing core fail the STREX of a core that already holds exclusive monitor on that address?

If I understand the global monitor state machine right, it doesn't. Instead, the matching STREX from second core will fail.


Top
 Profile  
 
 Post subject: Re: Progress guarantees of Arm LL/SC
PostPosted: Thu Jun 01, 2017 10:51 am 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 360
Icee wrote:
If I understand the global monitor state machine right, it doesn't. Instead, the matching STREX from second core will fail.
Great. That's nice to know. Looking at the quote, I see a subtle nuance, where the specs say "repeatedly contending", which might imply backoff heuristics. I doubt that it would be very practical though. The arbitration is probably implemented through the cache coherence. It doesn't even matter too much, if the progress is required by the architecture.

Thanks.


Top
 Profile  
 
 Post subject: Re: Progress guarantees of Arm LL/SC
PostPosted: Thu Jun 01, 2017 11:14 am 
Offline
Member
Member

Joined: Wed Jan 08, 2014 8:41 am
Posts: 100
Location: Moscow, Russia
You might also be interested in a related discussion in section 6.2 of Volume 1 of the RISC-V manual. It goes into more detail on how an actual implementation might guarantee forward progress in LR/SC contention scenario and indeed relies on cache line manipulation.


Top
 Profile  
 
 Post subject: Re: Progress guarantees of Arm LL/SC
PostPosted: Thu Jun 01, 2017 12:36 pm 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 360
@Icee: You probably meant section 5.2.

The idea is to apparently allow blocking implementations. That is, a core can keep the cache line exclusive for as long as necessary, stalling others in the meantime. Due to the syntactical constraints imposed on the code section guarded by LL/SC, the execution time of the blocker is always bounded. Hence the progress guarantee.

LL/SC ends up being not so much limited version of transnational memory, but a flexible/user-programmable version of x86 atomic instructions. Which does fit well with the RISC principles overall.

PS: Thanks again. I will try to RTFM next time.


Top
 Profile  
 
 Post subject: Re: Progress guarantees of Arm LL/SC
PostPosted: Fri Jun 02, 2017 4:22 am 
Offline
Member
Member

Joined: Wed Jan 08, 2014 8:41 am
Posts: 100
Location: Moscow, Russia
simeonz wrote:
@Icee: You probably meant section 5.2.

It's actually section 7.2 in the latest (v2.2) spec. The RISC-V people are very liberal about moving stuff around.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Majestic-12 [Bot] and 9 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group