[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 */
> r3)
> loadaddr 0f,r5
> 0:
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:
loadaddr fail,r5
load_tagged [r1],r4
xor r4,r2,r6
jump.nz r6,r5
store_tagged r3,[r1],r6
jump.z r6,r5
loadconsx $1,r1 // return true
jump r63
fail:
move r0,r1 // return false
jump r63
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
> 0:
> 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 majordomo@seul.org with
unsubscribe f-cpu in the body. http://f-cpu.seul.org/