Java example source code file (CycleDetectingLockFactoryTest.java)

This example Java source code file (CycleDetectingLockFactoryTest.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

establish, expected, locka, lockb, lockc, lockd, lockingthread, potentialdeadlockexception, readwritea, readwriteb, readwritec, reentrantlock, reentrantreadwritelock, regex, string, threading, threads

The CycleDetectingLockFactoryTest.java Java example source code

/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.util.concurrent;

import com.google.common.base.Joiner;
import com.google.common.util.concurrent.CycleDetectingLockFactory.Policies;
import com.google.common.util.concurrent.CycleDetectingLockFactory.Policy;
import com.google.common.util.concurrent.CycleDetectingLockFactory.PotentialDeadlockException;

import junit.framework.TestCase;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Unittests for {@link CycleDetectingLockFactory}.
 *
 * @author Darick Tong
 */
public class CycleDetectingLockFactoryTest extends TestCase {

  private ReentrantLock lockA;
  private ReentrantLock lockB;
  private ReentrantLock lockC;
  private ReentrantReadWriteLock.ReadLock readLockA;
  private ReentrantReadWriteLock.ReadLock readLockB;
  private ReentrantReadWriteLock.ReadLock readLockC;
  private ReentrantReadWriteLock.WriteLock writeLockA;
  private ReentrantReadWriteLock.WriteLock writeLockB;
  private ReentrantReadWriteLock.WriteLock writeLockC;
  private ReentrantLock lock1;
  private ReentrantLock lock2;
  private ReentrantLock lock3;
  private ReentrantLock lock01;
  private ReentrantLock lock02;
  private ReentrantLock lock03;

  @Override
  protected void setUp() throws Exception {
    super.setUp();
    CycleDetectingLockFactory factory =
        CycleDetectingLockFactory.newInstance(Policies.THROW);
    lockA = factory.newReentrantLock("LockA");
    lockB = factory.newReentrantLock("LockB");
    lockC = factory.newReentrantLock("LockC");
    ReentrantReadWriteLock readWriteLockA =
        factory.newReentrantReadWriteLock("ReadWriteA");
    ReentrantReadWriteLock readWriteLockB =
        factory.newReentrantReadWriteLock("ReadWriteB");
    ReentrantReadWriteLock readWriteLockC =
        factory.newReentrantReadWriteLock("ReadWriteC");
    readLockA = readWriteLockA.readLock();
    readLockB = readWriteLockB.readLock();
    readLockC = readWriteLockC.readLock();
    writeLockA = readWriteLockA.writeLock();
    writeLockB = readWriteLockB.writeLock();
    writeLockC = readWriteLockC.writeLock();

    CycleDetectingLockFactory.WithExplicitOrdering<MyOrder> factory2 =
        newInstanceWithExplicitOrdering(MyOrder.class, Policies.THROW);
    lock1 = factory2.newReentrantLock(MyOrder.FIRST);
    lock2 = factory2.newReentrantLock(MyOrder.SECOND);
    lock3 = factory2.newReentrantLock(MyOrder.THIRD);

    CycleDetectingLockFactory.WithExplicitOrdering<OtherOrder> factory3 =
        newInstanceWithExplicitOrdering(OtherOrder.class, Policies.THROW);
    lock01 = factory3.newReentrantLock(OtherOrder.FIRST);
    lock02 = factory3.newReentrantLock(OtherOrder.SECOND);
    lock03 = factory3.newReentrantLock(OtherOrder.THIRD);
  }

  // In the unittest, create each ordered factory with its own set of lock
  // graph nodes (as opposed to using the static per-Enum map) to avoid
  // conflicts across different test runs.
  private <E extends Enum CycleDetectingLockFactory.WithExplicitOrdering
      newInstanceWithExplicitOrdering(Class<E> enumClass, Policy policy) {
    return new CycleDetectingLockFactory.WithExplicitOrdering<E>(
        policy, CycleDetectingLockFactory.createNodes(enumClass));
  }

  public void testDeadlock_twoLocks() {
    // Establish an acquisition order of lockA -> lockB.
    lockA.lock();
    lockB.lock();
    lockA.unlock();
    lockB.unlock();

    // The opposite order should fail (Policies.THROW).
    PotentialDeadlockException firstException = null;
    lockB.lock();
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockB -> LockA", "LockA -> LockB");
      firstException = expected;
    }

    // Second time should also fail, with a cached causal chain.
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockB -> LockA", "LockA -> LockB");
      // The causal chain should be cached.
      assertSame(firstException.getCause(), expected.getCause());
    }

    // lockA should work after lockB is released.
    lockB.unlock();
    lockA.lock();
  }

  // Tests transitive deadlock detection.
  public void testDeadlock_threeLocks() {
    // Establish an ordering from lockA -> lockB.
    lockA.lock();
    lockB.lock();
    lockB.unlock();
    lockA.unlock();

    // Establish an ordering from lockB -> lockC.
    lockB.lock();
    lockC.lock();
    lockB.unlock();

    // lockC -> lockA should fail.
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "LockC -> LockA", "LockB -> LockC", "LockA -> LockB");
    }
  }

  public void testReentrancy_noDeadlock() {
    lockA.lock();
    lockB.lock();
    lockA.lock();  // Should not assert on lockB -> reentrant(lockA)
  }

  public void testExplicitOrdering_noViolations() {
    lock1.lock();
    lock3.lock();
    lock3.unlock();
    lock2.lock();
    lock3.lock();
  }

  public void testExplicitOrdering_violations() {
    lock3.lock();
    try {
      lock2.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "MyOrder.THIRD -> MyOrder.SECOND");
    }

    try {
      lock1.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "MyOrder.THIRD -> MyOrder.FIRST");
    }

    lock3.unlock();
    lock2.lock();

    try {
      lock1.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "MyOrder.SECOND -> MyOrder.FIRST");
    }
  }

  public void testDifferentOrderings_noViolations() {
    lock3.lock();   // MyOrder, ordinal() == 3
    lock01.lock();  // OtherOrder, ordinal() == 1
  }

  public void testExplicitOrderings_generalCycleDetection() {
    lock3.lock();   // MyOrder, ordinal() == 3
    lock01.lock();  // OtherOrder, ordinal() == 1

    lock3.unlock();
    try {
      lock3.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "OtherOrder.FIRST -> MyOrder.THIRD",
          "MyOrder.THIRD -> OtherOrder.FIRST");
    }

    lockA.lock();
    lock01.unlock();
    lockB.lock();
    lockA.unlock();

    try {
      lock01.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "LockB -> OtherOrder.FIRST",
          "LockA -> LockB",
          "OtherOrder.FIRST -> LockA");
    }
  }

  public void testExplicitOrdering_cycleWithUnorderedLock() {
    Lock myLock = CycleDetectingLockFactory.newInstance(Policies.THROW)
        .newReentrantLock("MyLock");
    lock03.lock();
    myLock.lock();
    lock03.unlock();

    try {
      lock01.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "MyLock -> OtherOrder.FIRST",
          "OtherOrder.THIRD -> MyLock",
          "OtherOrder.FIRST -> OtherOrder.THIRD");
    }
  }

  public void testExplicitOrdering_reentrantAcquisition() {
    CycleDetectingLockFactory.WithExplicitOrdering<OtherOrder> factory =
        newInstanceWithExplicitOrdering(OtherOrder.class, Policies.THROW);
    Lock lockA = factory.newReentrantReadWriteLock(OtherOrder.FIRST).readLock();
    Lock lockB = factory.newReentrantLock(OtherOrder.SECOND);

    lockA.lock();
    lockA.lock();
    lockB.lock();
    lockB.lock();
    lockA.unlock();
    lockA.unlock();
    lockB.unlock();
    lockB.unlock();
  }

  public void testExplicitOrdering_acquiringMultipleLocksWithSameRank() {
    CycleDetectingLockFactory.WithExplicitOrdering<OtherOrder> factory =
        newInstanceWithExplicitOrdering(OtherOrder.class, Policies.THROW);
    Lock lockA = factory.newReentrantLock(OtherOrder.FIRST);
    Lock lockB = factory.newReentrantReadWriteLock(OtherOrder.FIRST).readLock();

    lockA.lock();
    try {
      lockB.lock();
      fail("Expected IllegalStateException");
    } catch (IllegalStateException expected) {
    }

    lockA.unlock();
    lockB.lock();
  }

  public void testReadLock_deadlock() {
    readLockA.lock();  // Establish an ordering from readLockA -> lockB.
    lockB.lock();
    lockB.unlock();
    readLockA.unlock();

    lockB.lock();
    try {
      readLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockB -> ReadWriteA", "ReadWriteA -> LockB");
    }
  }

  public void testReadLock_transitive() {
    readLockA.lock();  // Establish an ordering from readLockA -> lockB.
    lockB.lock();
    lockB.unlock();
    readLockA.unlock();

    // Establish an ordering from lockB -> readLockC.
    lockB.lock();
    readLockC.lock();
    lockB.unlock();
    readLockC.unlock();

    // readLockC -> readLockA
    readLockC.lock();
    try {
      readLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "ReadWriteC -> ReadWriteA",
          "LockB -> ReadWriteC",
          "ReadWriteA -> LockB");
    }
  }

  public void testWriteLock_threeLockDeadLock() {
    // Establish an ordering from writeLockA -> writeLockB.
    writeLockA.lock();
    writeLockB.lock();
    writeLockB.unlock();
    writeLockA.unlock();

    // Establish an ordering from writeLockB -> writeLockC.
    writeLockB.lock();
    writeLockC.lock();
    writeLockB.unlock();

    // writeLockC -> writeLockA should fail.
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "ReadWriteC -> ReadWriteA",
          "ReadWriteB -> ReadWriteC",
          "ReadWriteA -> ReadWriteB");
    }
  }

  public void testWriteToReadLockDowngrading() {
    writeLockA.lock();  // writeLockA downgrades to readLockA
    readLockA.lock();
    writeLockA.unlock();

    lockB.lock();  // readLockA -> lockB
    readLockA.unlock();

    // lockB -> writeLockA should fail
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "LockB -> ReadWriteA", "ReadWriteA -> LockB");
    }
  }

  public void testReadWriteLockDeadlock() {
    writeLockA.lock();  // Establish an ordering from writeLockA -> lockB
    lockB.lock();
    writeLockA.unlock();
    lockB.unlock();

    // lockB -> readLockA should fail.
    lockB.lock();
    try {
      readLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "LockB -> ReadWriteA", "ReadWriteA -> LockB");
    }
  }

  public void testReadWriteLockDeadlock_transitive() {
    readLockA.lock();  // Establish an ordering from readLockA -> lockB
    lockB.lock();
    readLockA.unlock();
    lockB.unlock();

    // Establish an ordering from lockB -> lockC
    lockB.lock();
    lockC.lock();
    lockB.unlock();
    lockC.unlock();

    // lockC -> writeLockA should fail.
    lockC.lock();
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "LockC -> ReadWriteA",
          "LockB -> LockC",
          "ReadWriteA -> LockB");
    }
  }

  public void testReadWriteLockDeadlock_treatedEquivalently() {
    readLockA.lock();  // readLockA -> writeLockB
    writeLockB.lock();
    readLockA.unlock();
    writeLockB.unlock();

    // readLockB -> writeLockA should fail.
    readLockB.lock();
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "ReadWriteB -> ReadWriteA", "ReadWriteA -> ReadWriteB");
    }
  }

  public void testDifferentLockFactories() {
    CycleDetectingLockFactory otherFactory =
        CycleDetectingLockFactory.newInstance(Policies.WARN);
    ReentrantLock lockD = otherFactory.newReentrantLock("LockD");

    // lockA -> lockD
    lockA.lock();
    lockD.lock();
    lockA.unlock();
    lockD.unlock();

    // lockD -> lockA should fail even though lockD is from a different factory.
    lockD.lock();
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockD -> LockA", "LockA -> LockD");
    }
  }

  public void testDifferentLockFactories_policyExecution() {
    CycleDetectingLockFactory otherFactory =
        CycleDetectingLockFactory.newInstance(Policies.WARN);
    ReentrantLock lockD = otherFactory.newReentrantLock("LockD");

    // lockD -> lockA
    lockD.lock();
    lockA.lock();
    lockA.unlock();
    lockD.unlock();

    // lockA -> lockD should warn but otherwise succeed because lockD was
    // created by a factory with the WARN policy.
    lockA.lock();
    lockD.lock();
  }

  public void testReentrantLock_tryLock() throws Exception {
    LockingThread thread = new LockingThread(lockA);
    thread.start();

    thread.waitUntilHoldingLock();
    assertFalse(lockA.tryLock());

    thread.releaseLockAndFinish();
    assertTrue(lockA.tryLock());
  }

  public void testReentrantWriteLock_tryLock() throws Exception {
    LockingThread thread = new LockingThread(writeLockA);
    thread.start();

    thread.waitUntilHoldingLock();
    assertFalse(writeLockA.tryLock());
    assertFalse(readLockA.tryLock());

    thread.releaseLockAndFinish();
    assertTrue(writeLockA.tryLock());
    assertTrue(readLockA.tryLock());
  }

  public void testReentrantReadLock_tryLock() throws Exception {
    LockingThread thread = new LockingThread(readLockA);
    thread.start();

    thread.waitUntilHoldingLock();
    assertFalse(writeLockA.tryLock());
    assertTrue(readLockA.tryLock());
    readLockA.unlock();

    thread.releaseLockAndFinish();
    assertTrue(writeLockA.tryLock());
    assertTrue(readLockA.tryLock());
  }

  private static class LockingThread extends Thread {
    final CountDownLatch locked = new CountDownLatch(1);
    final CountDownLatch finishLatch = new CountDownLatch(1);
    final Lock lock;

    LockingThread(Lock lock) {
      this.lock = lock;
    }

    @Override
    public void run() {
      lock.lock();
      try {
        locked.countDown();
        finishLatch.await(1, TimeUnit.MINUTES);
      } catch (InterruptedException e) {
        fail(e.toString());
      } finally {
        lock.unlock();
      }
    }

    void waitUntilHoldingLock() throws InterruptedException {
      locked.await(1, TimeUnit.MINUTES);
    }

    void releaseLockAndFinish() throws InterruptedException {
      finishLatch.countDown();
      this.join(10000);
      assertFalse(this.isAlive());
    }
  }

  public void testReentrantReadWriteLock_implDoesNotExposeShadowedLocks() {
    assertEquals(
        "Unexpected number of public methods in ReentrantReadWriteLock. " +
        "The correctness of CycleDetectingReentrantReadWriteLock depends on " +
        "the fact that the shadowed ReadLock and WriteLock are never used or " +
        "exposed by the superclass implementation. If the implementation has " +
        "changed, the code must be re-inspected to ensure that the " +
        "assumption is still valid.",
        24, ReentrantReadWriteLock.class.getMethods().length);
  }

  private enum MyOrder {
    FIRST, SECOND, THIRD;
  }

  private enum OtherOrder {
    FIRST, SECOND, THIRD;
  }

  // Given a sequence of lock acquisition descriptions
  // (e.g. "LockA -> LockB", "LockB -> LockC", ...)
  // Checks that the exception.getMessage() matches a regex of the form:
  // "LockA -> LockB \b.*\b LockB -> LockC \b.*\b LockC -> LockA"
  private void checkMessage(
      IllegalStateException exception, String... expectedLockCycle) {
    String regex = Joiner.on("\\b.*\\b").join(expectedLockCycle);
    assertContainsRegex(regex, exception.getMessage());
  }

  // TODO(cpovirk): consider adding support for regex to Truth
  private static void assertContainsRegex(String expectedRegex, String actual) {
    Pattern pattern = Pattern.compile(expectedRegex);
    Matcher matcher = pattern.matcher(actual);
    if (!matcher.find()) {
      String actualDesc = (actual == null) ? "null" : ('<' + actual + '>');
      fail("expected to contain regex:<" + expectedRegex + "> but was:"
          + actualDesc);
    }
  }
}