RE: Proposal for sc_process_handle: AGREE

Bishnupriya, Philipp,

In writing up sc_process_handle::operator< I've hit another corner case.
First I'll re-state the rules we agreed, but reworded slightly:

(1) 2 valid handles are equal iff they are equivalent:
  if ( a.valid() && b.valid() )
    if( a == b)
      sc_assert( !(a < b) && !(b < a) );
    else
      sc_assert( (a < b) || (b < a) );

(2) a valid and an invalid handle are never equivalent:
  if( a.valid() && !b.valid() )
    sc_assert( (a < b) || (b < a) );

(3) 2 invalid handles are equivalent iff they formerly pointed to the same
process or no process object
  e.g.
  a = b = sc_get_current_process_handle();
  wait( a.terminated_event() );
  sc_assert( !(a < b) && !(b < a) );
  if( a.valid() ) // implementation dependent
    sc_assert( a==b );
  else
    sc_assert( a!=b );

  sc_process_handle a,b;
  sc_assert( !(a<b) && !(b<a) );
  sc_assert( a!=b );
 
Now the problem. When a process terminates, an implementation may chose to
invalidate a handle or not:

sc_process_handle p, q;
p = q = sc_spawn(...);

wait( p.terminated_event() );

if ( p.valid() && q.valid() )
{
  sc_assert( p == q );
  sc_assert( !(p < q) && !(q < p) ); // valid handles are equivalent
}
else if ( !p.valid() && !q.valid() )
{
  sc_assert( p != q );
  sc_assert( !(b < c) && !(c < b) ); // handles that formerly pointed to
the same process are equivalent
}
else // 1 handle valid, the other not
{
  sc_assert( p != q ); // One handle is invalid
  sc_assert( (p < q) || (q < p) ); ??????
}

Here we have two handles that point to the same process object, but only
one of them has been invalidated. By (2) they are not equivalent. By (3)
they would become equivalent once again when the 2nd handle gets
invalidated!

I guess we go in one of two directions:

* Either we keep (2), in which case two invalid handles are always
equivalent and (3) is wrong. Effectively there is an equivalence partition
for all invalid handles

* or two handles are equivalent iff they point or pointed to the same
process, in which case (2) need to be re-worded so it only applies where
the handles point to different processes.

Personally I vote for the first option (keep (2)), because this is
congruent with the fact that get_process_object() returns a null pointer
for an invalid handle. Effectively all process handles with a null pointer
are in the same equivalence partition. This would give us:

        strict means that H1 < H1 shall return false
 
        weak means that if H1 and H2 are both handles to the same
underlying process instance or are both invalid then H1 < H2 shall return
false and H2 < H1 shall return false
 
        ordering relation means that if H1 < H2 and H2 < H3 then H1 < H3
(whether H1, H2, or H3 are valid or invalid)

Thanks,

John A

From:
Bishnupriya Bhattacharya <bpriya@cadence.com>
To:
"Philipp A. Hartmann" <philipp.hartmann@offis.de>,
"john.aynsley@doulos.com" <john.aynsley@doulos.com>
Cc:
"jerome.cornet@st.com" <jerome.cornet@st.com>,
"systemc-p1666-technical@eda.org" <systemc-p1666-technical@eda.org>
Date:
24/03/2010 14:28
Subject:
RE: Proposal for sc_process_handle: AGREE

Philip, John,

Philip is right. My original code is correct and the text had the typo. It
should say

"the corner case of two invalid handles where the handles never did
point to any process objects need also be covered, and such handles
should be equivalent, and should not be equal (i.e. they should be
unequal)".

My apologies for the confusion.

John, are we on the same page now?

Thanks,
-Bishnupriya

-----Original Message-----
From: Philipp A. Hartmann [mailto:philipp.hartmann@offis.de]
Sent: Wednesday, March 24, 2010 5:57 PM
To: john.aynsley@doulos.com
Cc: Bishnupriya Bhattacharya; jerome.cornet@st.com;
systemc-p1666-technical@eda.org
Subject: Re: Proposal for sc_process_handle: AGREE

John, Bishnupriya,

a straight-forward implementation (e.g. based on unique ids with a "magic
id" 0 for empty handles) would lead to equivalent empty handles.
See below.

On 24/03/10 12:37, john.aynsley@doulos.com wrote:
> Bishnupriya,
>
> You wrote
>
> I agree that using an unique integer id for each process object will
> allow an invalidating implementation to implement operator <
> correctly, as laid down below in Philip's 3 bullet points. Note that
> the corner case of two invalid handles where the handles never did
> point to any process objects need also be covered, and such handles
> should not be equivalent, and should not be equal (i.e. they should be
unequal)
> sc_process_handle a,b;
> sc_assert(!(a<b) && !(b<a));
> sc_assert(a!=b);

This original code is what I would have expected: empty handles are
unequal (as per current standard), but equivalent (neither is "less than"
the other).

> I think you meant:
>
> sc_process_handle a,b;
> sc_assert( (a<b) || (b<a) );

In this case, you could fill up a map with empty handles indefinitely (and
never find empty handles in such a container):

std::map< sc_process_handle, int > m;
sc_process_handle no_proc;

for( int i=0; i<10; ++i )
   // always adds a new entry to the map :(
   m[ no_proc ]++;

So I think, the original code example of Bishnupriya has been correct, and
the explaining text contained a typo. Am I right?

Greetings from Oldenburg,
Philipp

[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.