How to test lock mode compatibility?

[Adam Retter]

Roman,

I adopted an existing lock implementation, and I want prove that it is
either correct or incorrect.

I did actually start by writing some simple compatibility tests. I
used two threads and a CountDownLatch, both threads must acquire their
respective modes for the latch to countdown from two to zero, at zero
the test completes by asserting the lock modes are compatible. The
test also has a timeout, where if it does not complete within the
time, it determines that the lock modes were incompatible. The
implementation is probably naive, but I hoped that it proved some
initial correctness -
https://github.com/adamretter/java-multilocks/blob/master/src/test/java/uk/ac/ic/doc/slurp/multilock/CompatibilityTest.java#L195

I am by no means a concurrency or locking expert! My fear was that the
order of operations in those simple tests was too predictable. I
wanted to use JCStress so that my lock's Sync
(AbstractQueuedLongSynchronizer) implementation was thoroughly tested,
i.e. it should be unpredictable when threads enter tryAcquireShared
and tryAcquired, and where they are within the bounds of those
methods. Does that make sense?

It may be that there are better ways to test this, and I would be
interested to further understand them...
On Fri, 31 Aug 2018 at 23:40, Roman Leventov <leventov.ru at gmail.com> wrote:
>
> Hi Adam, why do you want to test lock mode compatibility with JCStress? You could write linearizable code (even single threaded, or involving multiple threads if your locks are reentrable or recognize the owner thread), modelling exactly the sequence of actions that you want to test.
>
> On Fri, 31 Aug 2018, 12:58 Adam Retter, <adam.retter at googlemail.com> wrote:
>>
>> Hi there,
>>
>> I am trying to write some tests to check the compatibility of lock
>> modes. I have an experimental lock implementation which has more modes
>> that the typical: shared and exclusive.
>>
>> I am struggling a little to realise the best way to write tests for
>> checking lock mode compatibility with JCStress.
>>
>> I will use Java's ReentrantReadWriteLock to illustrate my point, as it
>> is likely that we are all familiar with it!
>>
>> I think the lock compatibility matrix for ReentrantReadWriteLock's
>> lock modes, looks like this:
>>
>>    | S      | X
>> -----------------
>> S | YES | NO
>> X | NO   | NO
>>
>> i.e. if Thread 1 holds the shared (read) lock, then Thread 2 can
>> simultaneously hold the shared (read) lock, or vice-versa.
>>
>> I would like to write some JCStress tests to prove the compatibility
>> of the lock modes.
>>
>> I can see a simple mechanism for testing this via the #tryLock() methods:
>>
>> public class ReentrantReadWriteLockBooleanCompatibilityTest {
>>
>>     @State
>>     public static class S {
>>         public final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
>>
>>         public boolean shared() {
>>             return lock.readLock().tryLock();
>>         }
>>
>>         public boolean exclusive() {
>>             return lock.writeLock().tryLock();
>>         }
>>     }
>>
>>     @JCStressTest
>>     @Outcome(id = "true, true", expect = Expect.ACCEPTABLE, desc = "T1
>> and T2 are both acquired S")
>>     public static class S_S {
>>         @Actor
>>         public void actor1(S s, ZZ_Result r) { r.r1 = s.shared(); }
>>         @Actor
>>         public void actor2(S s, ZZ_Result r) { r.r2 = s.shared(); }
>>     }
>>
>>     @JCStressTest
>>     @Outcome(id = "true, false", expect = Expect.ACCEPTABLE, desc =
>> "T1 acquired S, and T2 could not acquire X")
>>     @Outcome(id = "false, true", expect = Expect.ACCEPTABLE, desc =
>> "T2 acquired X, and T1 could not acquire S")
>>     public static class S_X {
>>         @Actor
>>         public void actor1(S s, ZZ_Result r) { r.r1 = s.shared(); }
>>         @Actor
>>         public void actor2(S s, ZZ_Result r) { r.r2 = s.exclusive(); }
>>     }
>>
>> // ...further tests for X_S and X_X omitted for brevity
>> }
>>
>> However, the above involves not releasing the locks, which is fine for
>> #tryLock because it is non-blocking, but will not work for #lock(). As
>> such, I am struggling to devise a meaningful way to test with #lock()
>> instead of #tryLock().
>>
>> 1. For compatible modes I can think of describing the test I want as:
>> Whilst a thread holds a S mode lock, another thread should be able to
>> acquire the S mode lock.
>> 2. For incompatible modes as: Whilst a thread holds the X mode lock,
>> no other thread should be able to acquire the X (or S mode) lock.
>>
>> I am not quite sure of the correct way to detect when two threads both
>> hold shared (read) mode locks.
>> Although, one approach that occurred to me would be to have both
>> threads increment a shared int. Outcomes might be detectable as:
>> a) If there are "lost updates" to the int, it would show that it was
>> updated simultaneously by two threads holding locks with compatible
>> (shared) modes.
>> b) If there are no "lost updates", then the threads must not have had
>> compatible modes.
>> However, I don't feel entirely comfortable with that approach, as with
>> (a) I think it would be possible to do the unsynchronized updates to
>> the int without always exhibiting "lost updates", so we would have a
>> false-positive.
>>
>> Can someone suggest a sensible way to do these compatibility checks?
>>
>>
>>
>> --
>> Adam Retter
>>
>> skype: adam.retter
>> tweet: adamretter
>> http://www.adamretter.org.uk



-- 
Adam Retter

skype: adam.retter
tweet: adamretter
http://www.adamretter.org.uk