TL2 read-set validation

[Elad]

Hi Guy,

I have a question about the read-set validation in the TL2 commit
phase.
it seems to me that when the read set is validated it only checks the
version of the lock and doesn't check if it is locked
(ReadSet.CheckClock).

I'd like to know if I'm missing something here or is the lock check
necessary?

Thanks,
Elad.

[Tovi Almozlino]

It seems to me that once a transaction has reached the commit phase, it doesn't need to care about a read field's lock. It's already read the field's value during its speculative execution.

If the field is now locked by another transaction, then that can mean one of two things:

Either

1) It hasn't been changed yet by the other transaction. No problem.

2) It has been changed. But the new value is irrelevant to the original transaction, since its actual execution never saw it. Nor can anyone else see the new value until the field is unlocked. And of course, if the field is locked and then unlocked, the version will have changed and the original transaction would abort in that case.

[Guy Korland]

Check the TL2 paper for more details.

--
You received this message because you are subscribed to the Google Groups "Deuce-STM developers" group.

To view this discussion on the web visit https://groups.google.com/d/msg/deuce-stm-developers/-/F2hcmsC7tpYJ.

To post to this group, send email to deuce-stm-...@googlegroups.com.
To unsubscribe from this group, send email to deuce-stm-develo...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/deuce-stm-developers?hl=en.

[Tovi Almozlino]

In the TL2 paper, it does actually specifically mention checking the lock during the commit-time readset validation.

Still, it seems there is some controversy here. In Yoav's contention management TL2 implementation, he doesn't check the locks of the readset during the commit.

[Yoav Cohen]

Hi Tovi, Elad,

It is necessary to check that the locks of the memory locations the
transaction read are not locked as part of validating the readset.
This issue was raised a few weeks ago by Dmitri Perelman from the
Technion and Guy already fixed the bug in TL2 and I haven't done so
yet (but promise to do it very soon).

Not checking that the locks are locked breaks the linearizability of
the STM system. I will give you an example. Suppose we have two memory
locations, x=10 and y=20 and two transactions executed concurrently by
two threads, T1 and T2. T1 performs y=x*3 (reading x and writing to y)
and T2 performs x=y+1 (reading y and writing to x). Now, both threads
run concurrently and reach their commit protocol. T1 locks y and T2
locks x. Since they don't check that the memory locations in their
read sets are not locked, both validate their read-sets successfully.
Now we have two options: either T1 commits first or T2 commits first.
Let's assume T1 commits first. So after T1's commit we have x=10 and
y=30 (10*3) and then T2 commits and we have x=21 (20+1) and y=30. This
execution history is not linearizable, since you can't re-order it
somehow to be correct: T1 and T2 didn't execute any code that can take
x=10,y=30 and turn it into x=21 and y=30. More specifically, x=21 and
y=30 is a result of T2 viewing an inconsistent state of memory where
x=20 and y=30 (there is no code in our application that can generate
the state x=20,y=30 from x=10,y=20).

It's tricky, I admit (took me a few minutes to come up with the
example).

Cheers,
Yoav.

[Tovi Almozlino]

You're right. I guess now you have to add some new lock-stealing code there...

[Tiago Vale]

Checking the locks isn't enough.

Since the commit algorithm is

1. lock write set
   
2. check read set

we actually need to know more information about the locks, namely for each lock which transaction holds it.
If transaction T both reads and writes a memory location m, step 1 will lock m while step 2 will cause T to abort because m's lock is held. This is clearly undesired and I believe explains why I can't run any benchmark with TL2 since [2], since any transaction which reads and writes to the same memory location will abort itself.

[1] https://github.com/DeuceSTM/DeuceSTM/issues/1

[2] https://github.com/DeuceSTM/DeuceSTM/commit/da6321d41132e8232cbfee96dc37e0a267fc6e94

[FM]

Tiago,  

You are right and the scenario that you are reporting is already published in the Issue 60 (http://code.google.com/p/deuce/issues/detail?id=60). I agree with you and I think the fix for this problem requires more knowledge about the locks, namely which transaction holds each lock.

So, I made a proposal to fix the Issue 60, that includes an additional parameter: byte[] contextLocks, in the method checkLock. Then this method can perform a validation to check for self-locking. I used the same test algorithm that is already made in the lock method of the same class.

I am currently using this fix in my tests with TL2 and now I can run successfully the StmBench7 and STAMP benchmarks.

Regards,

Fernando Miguel Carvalho

[Guy Korland]

Notice: All the issues management moved to GigtHub see: https://github.com/DeuceSTM/DeuceSTM/issues/15

Also, please feel free to fork the code and send a pull request and I'll merge it.

Guy

--

You received this message because you are subscribed to the Google Groups "Deuce-STM developers" group.

To view this discussion on the web visit https://groups.google.com/d/msg/deuce-stm-developers/-/kXw78LjYhEwJ.

To post to this group, send email to deuce-stm-...@googlegroups.com.
To unsubscribe from this group, send email to deuce-stm-develo...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/deuce-stm-developers?hl=en.

--
Regards,
Guy Korland

[FM]

Ok, I have already done a pull request with a fix proposal to the issue 15.

[Tiago Vale]

Thanks!

Regarding running STMBench7, you're instrumenting rt.jar right? What are the contents of the org.deuce.{exclude,include} properties that you're using?

[FM]

Yes, I need to instrument the Java runtime library (rt.jar) and I use the following exclude statement both in the offline instrumentation and also during the execution of the StmBench7, because the Deuce runtime should avoid the invocation of the transactional methods for classed that have been excluded.

-Dorg.deuce.exclude=sun.*,java.lang.Thread,java.lang.ThreadLocal,java.lang.Exception,java.lang.Class,java.lang.System,java.lang.Enum