[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [f-cpu] Conditionnal Load and Store




----- Original Message -----
From: "Yann Guidon" <whygee@f-cpu.org>
To: <f-cpu@seul.org>
Sent: Friday, July 26, 2002 9:35 PM
Subject: Re: [f-cpu] Conditionnal Load and Store


> hi,
>
> Christophe Avoinne wrote:
> > ----- Original Message -----
> > From: "Yann Guidon" <whygee@f-cpu.org>
> > > hi,
> > >
> > > <snip>
> > >
> > > conditional loads/stores are a corollary of the conditional moves.
> > >
> > > IIRC it appeared that these instructions were in fact needed,
> > > when we were discussing about the semaphores done with LL/SC.
> > > "Store conditional" is this thing.
> > >
> > > By the way : condition 3 is still reserved for FP, but we could
> > > simply connect it to the LSU : LL/SC would then not need any specific
> > > opcode. it sounds easy and logical, what do others think ?
> >
> > I don't really understand how you plan to do so.
> >
> > retry:
> > LL [r1],r2 ==> loading [r1] in r2 and set a lock bit in matching LSU
entry.
> > ...
> > SC r2,[r1],r3 ==> storing r2 in [r1] if lock bit in matching LSU entry
is
> > set and set r3 to 1, otherwise just set r3 to 0. Then lock bit in
matching
> > LSU entry is reset.
> > IF (r3 == 0) JUMP ... // goto retry;
> >
> > As you can see, you need to set this special bit with a LOAD operation
and
> > check it and report it in register with a STORE operation
> >
> > So I wonder how you can use condition 3 with LOAD/STORE to do so since
STORE
> > would also need to report if storing really occured or not..
>
> mmmh i see.
> My idea goes as follows :
> The condition is an "attribute" of the condition register, which
> can be tested with move and jmp as well. Like the "zero" flag,
> it is regenerated everytime something related happens.
> So the information of whether the store really occured needs not to
> be duplicated. The only "problem" is that it is a "volatile" flag,
> so it might yield false negatives.

In fact, most pair LL/SC are used in a conditional loop as the following
example :

int atomic_add (int *slot,int delta) {
    int old_value;
     // we must loop until we are able to store the new value in slot
    do {
        old_value = ll(slot);
    } while (!sc(old_value + delta,slot));
    return old_value; // the very last value we read before really changing
it
}

As you can see, we really need to know if 'sc' succeeds in storing when
called. If we cannot have this info, we would have bad behavior :

int atomic_add_unsafe (int *slot,int delta) {
    int old_value = *slot;
    do {
        old_value = ll(slot);
        sc(old_value + delta,slot);
    } while (*slot != old_value + delta);
    return old_value; // the very last value we read before really changing
it
}

This second example has a drawback : someone can have changed the value of
slot, just after 'sc', so we loop again for nothing !

Worse : A enters function with delta = 1 and is switched off just before
'sc' for B. B also enters functions with delta = 1, executes 'll' then 'sc'
which succeeds. When A resumes, its 'sc' aborts (normal behavior) but the
while condition *slot != old_value + delta is false (because 'sc' cannot
instruct its abort) because it still believes its old_value is good (whereas
it must be refetched). In fact our function atomic_add_unsafe really fails
to be atomic in certain condition.

Now are you convinced why you absolutely need to instruct if 'sc' succeeds
or not ? and why despite this info looks like redundant (duplicated) it is
necessary ?

Now I can state : 'sc' is not a simple conditional store. In fact, 'sc'
cannot only be replaced with a conditionnal store.

> Your idea is a bit different because it includes "persistent" data.
> it has drawbacks and advantages. the drawback comes from the fact
> that the decision history is made "static" or "persistent".

What is persistent ? the lock bit in LSU is reset (so it is in fact very
volatile) when executing 'sc' so you need to save it somewhere (i.e, in a
register) before resetting it, so we can know which action to take after a
'sc'.

> One problem is that the condition in your code is at the place
> of R2, and a specific SC is not desired if we add the generic
> "conditional store" instruction.

I know but as I told you, 'sc' cannot be replaced with a simple conditionnal
store.

> The real big problem is that in this instruction, the condition
> and the pointer are the same register => should not need to be
> duplicated...

Which instruction ?

Sorry to say, you cannot escape this apparent duplication, if you really
want a ll/sc mechanism.

> There is something i miss, but i don't know what...

I think so.


*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/