RE: [abc] oopsla outline

From: Eric Bodden <eric.bodden@mail.mcgill.ca>
Date: Thu Mar 02 2006 - 16:22:00 GMT

> Pavel says he couldn't get jhotdraw to terminate
> when instrumented with j-lo. you mentioned you made
> some improvements, so perhaps you could try again?
> If necessary, recommend a number of iterations that
> can be processed by j-lo, so we can use that number
> for the other versions.

Ok, I will.
 
> Does your version produce
> memory measurements in the same way as the other versions do?
> Generally, it would be great if the j-lo version was
> ready for comparison both in time and space.
>
> * get hawk to process jhotdraw+safeenum? I guess our
> only hope is Klaus willing to help out.

Yes. I keep on bugging him but still no answer :-/
 
> * hashcode tm on approve:
> does abc now properly process approve? You mentioned
> earlier that you made it skip some problematic class.
> If that is still so, have you checked that class does
> not contain any hashing-related stuff?

It runs now by replacing three classes. I have not checked if they
contain related stuff. I will do so.
 
> * lock order reversal.
> Nobody on this end understands the tracematch you wrote -
> you've thought about this problem before, but we haven't.
> Can you send a careful explanation to the list, starting
> with the problem, a few examples where it should match
> and shouldn't, and so on. Sorry to be slow!

A lock order reversal is a pattern that should warn developers: When
this pattern occurs it means that a deadlock *could* have occurred *if*
threads would have been scheduled in a slightly different way. This
makes sense, because there is no point in reporting *actual* deadlocks
because when the program deadlocks you cannot report that any more.

Hence one tries to match whenever there exists a thread t1 which locks
resources r1,r2 in the order r1 and then r2 and also there exists
another thread t2 which locks them in the inverse order. Because then,
in the case lock(t1,r1) lock(t2,r2) lock(t1,r2) lock(t2,r1) the system
would deadlock. (Note that the lock symbol matches the event of *trying*
to acquire a lock. It is not said if this lock is ever actually
acquired.)

The current pattern looks as follows (where "lij" means thread I locks
resource j):

              (l11 l12 (u11 | u12 | l11 | l12)* l22 (u11 | u12 | l11 |
l12)* l21)
        | (l11 l22 l12 (u11 | u12 | l11 | l12)* l21)
        | (l11 l22 l21 (u21 | u22 | l22 | l21)* l12)
//the following cases can be omitted because they are symmetric to the
ones before
// | (l22 l11 l21 (u21 | u22 | l22 | l21)* l12)
// | (l22 l21 (u21 | u22 | l22 | l21)* l11 (u21 | u22 | l22 |
l21)* l12)

The first line handles cases where first t1 locks both resources, first
r1 then r2. Afterwards we do not care if it unlocks them again or locks
them again: They have been locked in that order and that counts. Then we
have an l22, followed by an l21 (again ignoring whatever thread 1 does
in between), which means thread 2 has locked the resources in the
ibverse order.

The second line handles the interleaved case where we have l11 (thread
1) then l22 (thread2) and then l12 followed by l21. Again, resources are
locked in the inverse order, but now interleaved. After thread 1 has
locked both resources (i.e. after l12), again we ignore further events
related to thread 1.

The third line handles the last case, l11 l22 l21 l12, where locking is
nested, i.e. first t1 takes a lock then t2 does locking and then t1
takes a lock again.

Lines 4 and 5 sepcify lines 3 and 2 respectively for the cases where t1
and t2 are swapped. Since TMs match on *all* possible valuations anyway,
we do not need those lines: We already have both possible bindings
anyway.

Does this make sense?

> Can you post the results of running it, so we can all see
> both time and memory behaviour? [we especially want to
> know about the second column :-)]

I will.

> Is this problem expressible in PQL? It would be really
> good if we could run a comparison!

I would be surprised if it was not. However, I have no experience at all
with PQL...
 
> In the meantime, Julian and Pavel are working round the clock
> to get indexing finished.
>
> Ganesh is implementing thisJoinPointIdentity for use in the
> Jigsaw locknunlock-in-same-method variations, to determine
> whether a backend optimisation of thisJoinPoint would be worthwhile.
>
> Neil is in charge of the "third table" (on the different ways
> of expressing CFL properties, via thisJP+cflow, via
> cflowdepth, and lots of other ways. He is also preparing the
> AOSD talk on open modules.

Great.

Today I am still very busy with a lecture and a 3h tutorial :-/ But I
will try to get this done ASAP. I will take the whole weekend off solely
for this kind of stuff.

Eric
Received on Thu Mar 02 16:22:07 2006

This archive was generated by hypermail 2.1.8 : Tue Mar 06 2007 - 16:13:27 GMT