[deuce-stm] TL2 Implementation Question

[Joseph]

Hi,
I have a question about the implementation of TL2 provided with the
deuce framework. The commit method releases locks in the same loop as
the actual writes to memory (i.e.,)

//publish values to shared memory
for( WriteFieldAccess writeField : writeSet){
writeField.put(); // commit value to field
LockTable.setAndReleaseLock( writeField.hashCode(), newClock,
locksMarker);
}

Is it possible for a hashing conflict between two fields in the same
transaction to cause the lock to be released too early? Or am I
missing something? To state the question another way, should the
release of the locks be split from the write backs to memory?

for( WriteFieldAccess writeField : writeSet){
writeField.put(); // commit value to field
}

for( WriteFieldAccess writeField : writeSet){
LockTable.setAndReleaseLock( writeField.hashCode(), newClock,
locksMarker);
}

Joe

--
You received this message because you are subscribed to the Google Groups "Deuce-STM" group.
To post to this group, send email to deuc...@googlegroups.com.
To unsubscribe from this group, send email to deuce-stm+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/deuce-stm?hl=en.

[Guy Korland]

It seems like you have a point here.

I'll have to check this, how did you get to this? Do you have a test case that failed?

Guy

[Michael Spear]

Guy,

There's a related potential bug (haven't worked through the details)
based on the use of a counter to track the number of locks that are
acquired. A lock that is "acquired" twice is, of course, not locked
the
second time, but the counter is incremented twice. If the
transaction
aborts, then it might try to unlock the same lock twice. Some bad
interleavings with a concurrent writer are technically possible.

In RSTM, we use a separate lock set. Only a successful lock acquire
leads to the lock being added to the lock set, and then to release
all
locks (as in the case Joe mentioned below, but also in the case of
aborts), we iterate through the lock set, not the write set. In
addition to the code being easier to understand w.r.t. correctness in
the face of hashing, this approach avoids hashing writeset entries
multiple times. In C++, it proved to be faster, but in Java, the
overheads may tip the scales in favor of a counter-based approach,
such
as that currently in DeuceSTM's TL2 implementation.

- Mike Spear

[Pascal Felber]

Hi Mike,

Joe is right about the first problem, and I think you are also correct about the second one. As TL2 releases the lock by a simple write (no CAS), when you release a lock twice you might end up releasing a lock that has been acquired by another thread in the meantime.

I checked in the LSA context and it doesn't seem to be affected by any of there problems. (But I would need to spend some time making the code faster and incorporating some of the optimizations we have in the C version.)

Cheers,

Pascal

[Joseph]

Well, I wish I could take credit for spotting this, but really it was
Professor Spear :-)

No, I don't have a specific test case that failed. We were discussing
how to modify your implementation of TL2 in order to provide ALA
semantics.

> > deuce-stm+...@googlegroups.com<deuce-stm%2Bunsu...@googlegroups.com>
> > .

> > For more options, visit this group at
> >http://groups.google.com/group/deuce-stm?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups "Deuce-STM" group.
> To post to this group, send email to deuc...@googlegroups.com.
> To unsubscribe from this group, send email to deuce-stm+...@googlegroups.com.

> For more options, visit this group athttp://groups.google.com/group/deuce-stm?hl=en.

[David Dice]

On Thu, Apr 22, 2010 at 11:49 AM, Joseph <joseph....@gmail.com> wrote:

Well, I wish I could take credit for spotting this, but really it was
Professor Spear :-)

No, I don't have a specific test case that failed. We were discussing
how to modify your implementation of TL2 in order to provide ALA
semantics.

With respect to stronger semantics, some of the modifications to TL2 to provide implicit privatization might be of interest.  Search for TL2-IP in http://blogs.sun.com/dave/resource/Transact2009-TLRW-ByteLock-Feb6.pdf.    (Note that for that form the commit operation needs to complete the write-back before dropping any of the locks covering the write-set).  

Regards

Dave

 

[Guy Korland]

Hi Joe,

I just committed a fix to the trunk.
If you have time please check out the code.

Thanks,
Guy Korland