Re: Proposal for sc_process_handle

Philipp,

I agree with your analysis so far, but the problem I am imagining starts
right there...

Suppose we have 2 handles to the same dead process:

a.valid == false
b.valid == false
(a == b) == false
!(a < b) && !(b < a)

We then create a new process and a handle to it

c.valid = true
(c == a) == false
(c == b) == false

Unfortunately, the new process object just happens to have the same
address as the dead process (a reincarnated zombie)

!(b < c) && !(c < b)
!(c < a) && !(a < c)

So, assuming our std::map still contains handle a, the new handle c cannot
be inserted into the map because it falls into the same equivalence
partition as a and b. As long as the map cataloguing our processes
includes an (invalid) handle to the dead process, it cannot include any
handle to the new process (the reincarnated zombie). If we were to clean
out all the invalid handles from the map, we could then insert a new valid
handle to the process. On the other hand, if process objects never get
deleted, so their storage never gets re-used, the problem does not arise.

I suppose the fix is to add a unique id (say 64 bits) to the process
object that does not get recycled within a single simulation run, and base
equivalence on that.

Cheers,

John A

From:
"Philipp A. Hartmann" <philipp.hartmann@offis.de>
To:
john.aynsley@doulos.com
Cc:
"systemc-p1666-technical@eda.org" <systemc-p1666-technical@eda.org>
Date:
18/03/2010 18:52
Subject:
Re: Proposal for sc_process_handle

John,

On 18/03/10 19:29, john.aynsley@doulos.com wrote:
>
> Re. the wording, you can leave that to me (though I appreciate any
suggestions).

Ok. I think, the tricky part here is to clarify the expected behaviour
in terms of handles, that have been invalidated.

> Re. the reincarnation, I'm not so sure (though I haven't thought about
> it in great depth). When a process dies, any handles are invalidated,
> and operator== would return false when comparing two handles both of
> which point to the same corpse. But the ordering would still be based on
> the dangling pointers.....

Yes. So it may be possible, that there are invalid handles with the
following properties (let a,b be two handles to the same, now terminated
process in an invalidating implementation):

( a != b ) == true
( a == b ) == false
( !( a < b ) && !( b < a ) )

The last bullet is essentially saying, that a and b are equivalent
according to the strict weak ordering. That is exactly what we want,
since they both refer to the same (dead) process object. Still, they
are invalid. So they are no longer "really" equal.

For the use as a key in a map, the equivalence is important. Otherwise
we would break the map's invariants (and even retains it, if the process
is reincarnated). The inequality (operator==/!=) may look weird, but is
at least consistent.

We may need a note, covering this specific behaviour, though.

Greetings from Oldenburg,
Philipp

> -----"Philipp A. Hartmann" <philipp.hartmann@offis.de> wrote: -----
>
>
> To: john.aynsley@doulos.com
> From: "Philipp A. Hartmann" <philipp.hartmann@offis.de>
> Date: 03/18/2010 06:12PM
> Cc: "systemc-p1666-technical@eda.org" <systemc-p1666-technical@eda.org>
> Subject: Re: Proposal for sc_process_handle
>
> On 18/03/10 12:22, john.aynsley@doulos.com wrote:
>> Whoops. If a dead process object gets reincarnated as another process
with
>> another handle, haven't we got a problem? The new process would have
>> equivalent ordering to the dead process, no?
>
> Hmmm, I think this shouldn't be a problem. At least, it has to be
> consistent with operator==, right?
>
> If it's really the same process object, then the handles would've been
> valid all the time (even though temporarily terminated). New handles,
> that still compare equal to the old ones are naturally ordered in the
> same way, as they still point to the same (now maybe reincarnated)
> process object.
>
> If its a new process object (with new handles comparing unequal to the
> old handle), then a different ordering is both expected and required, I
> think.
>
>> From: john.aynsley@doulos.com
> [snip]
>> Date: 18/03/2010 11:09
> [snip]
>
>> Agreed. Cool. Swap too.
>
> Glad to hear. :-)
>
>> I would probably want to spell out "strict weak ordering" and
"collation
>> order" rather than relying on familiarity with the C++ standard.
>
> Ok. I can try to provide an updated/more explicit wording. But this
> will have to wait until next week, as I'm quite busy (and out of
> office) until Tuesday, I suppose.
>
>> Just to be concrete, the following implementation...
>>
>> bool operator< (const sc_process_handle& r) const {
>> return this->get_process_object() < r.get_process_object();
>> }
>>
>> would work fine, provided the implementation left the dangling pointers

>> unchanged following invalidation, right?
>
> Exactly.
>
> Greetings from Oldenburg,
> Philipp
>
>> (But I agree that the
>> implementation should be free to implement "strick weak ordering"
however
>> it likes, and I agree the order could vary from run-to-run.)
>
> [snip]
>

-- 
Philipp A. Hartmann
Hardware/Software Design Methodology Group
OFFIS
R&D Division Transportation | FuE-Bereich Verkehr
Escherweg 2 · 26121 Oldenburg · Germany
Phone/Fax: +49-441-9722-420/282 · PGP: 0x9161A5C0 · http://www.offis.de/
-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.