Re: [f-cpu] CAS in FC0

[Michael Riepe <michael@stud.uni-hannover.de>]

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/