[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [f-cpu] CAS in FC0
On Wed, Mar 20, 2002 at 12:47:39AM +0100, Christophe wrote:
> Your tag is set with the instruction "load tag", but when someone write at the
> same word, you must clear this tag so the "store conditional" would be warned
> that someone else takes priority. Any "store" (conditional or not) at this word
> must clear this tag.
That's it, in a nutshell.
> > > I often wondered if it was worth it to add a conditional store, but now
> > > i'm convinced. Except that we need a version that checks the "tag".
> I'm pleased to hear you :). What you are speaking about is in fact "ll/sc"
> (load-linked/store-conditional), what i spoke about in the french mailing-list.
Where does this ll/sc nomenclature come from?
> how to implement a software CAS :
> // int CAS (int * /* pointer */ r1,int /* old value */ r2,int /* new value */
> loadaddr 0f,r5
loopentry r5 // ;-)
> move r2,r4
> load_tagged [r1],r2 // r2 : read value and set tag for [r1]
> xor r2,r4,r6
> jump.nz r6,r0,r5 // the value is not that we expect !
> store_tagged r3,[r1],r6 // r3 : value to write into [r1] if tag still set
> (tag is cleared afterward)
> jump.z r6,r0,r5 // tag was cleared before our store !
> nxor r2,r0,r3 // r3 != 0 if [r1] == r2 until writing r3
> into [r1]
> jump r0,r63 // return to caller with result in R1
I agree, with one exception: this is already a `CAS in a loop'.
A single CAS probably looks like this:
loadconsx $1,r1 // return true
move r0,r1 // return false
There's one problem left here: when the compare fails, the tag is not
cleared before the function returns (due to the jump before store_tagged).
> how to implement a PUSH :
> loadaddr 0f,r5
> move r2,r3 // our node address to push
> load_tagged [r1],r2 // read top
> store r2,[r3] // node->link = top
> store_tagged r3,[r1],r4 // top = node
> jump.nz r4,r0,r63 // return to caller if ok
> jump r0,r5
Yep. But beware! `store r2,[r3]' must not clear the tag, or else this
function will loop forever.
> > If a task switch (or IRQ service) occurs between load_tag and
> > store_locked, the tag may change behind the program's back (it might
> > be cleared and set again - the ABA problem). In order to avoid that,
> > a task switch should reset all tags.
> Yes, that's the main backdraft.
> > Oh btw: store_locked must return an indication that the store succeeded
> > (that is, it's a 3r1w instruction), and of course it has to clear the tag.
I guess we're going to get it right :)
One more point to consider: Do we really need an extra load_tag?
Tagging could as well be done for all loads.
Michael "Tired" Riepe <Michael.Riepe@stud.uni-hannover.de>
"All I wanna do is have a little fun before I die"
To unsubscribe, send an e-mail to email@example.com with
unsubscribe f-cpu in the body. http://f-cpu.seul.org/