DeadlockDetector { public Set<Transaction> victims() { int detectionId = detectionCounter++; LOG.log(Level.INFO, "Starting deadlock detection {0}", detectionId); Set<Transaction> victims = new HashSet<Transaction>(); Map<Transaction, WaitsFor> dependencies = lockManager.dependencies(); List<Path> paths = new ArrayList<Path>(); for (WaitsFor waitsFor : dependencies.values()) { paths.add(new Path(waitsFor)); } int extensions = 0; List<Path> cycles = new ArrayList<Path>(); logPaths(detectionId, 0, paths, cycles); do { for (Iterator<Path> pathIterator = paths.iterator(); pathIterator.hasNext();) { Path path = pathIterator.next(); Transaction pathLast = path.last(); WaitsFor extension = dependencies.get(pathLast); if (extension == null) { pathIterator.remove(); } else if (!path.extend(extension.copy())) { cycles.add(path); pathIterator.remove(); } } logPaths(detectionId, ++extensions, paths, cycles); } while (!paths.isEmpty()); for (Path path : cycles) { victims.add(path.victim()); } return victims; } DeadlockDetector(LockManager lockManager); Set<Transaction> victims();  }
@Test public void testEmpty() { DeadlockDetector deadlockDetector = new DeadlockDetector(lockManager); assertTrue(deadlockDetector.victims().isEmpty()); }
@Test public void testOneWaiter() throws Exception { a.lock(key(0)); DeadlockDetector deadlockDetector = new DeadlockDetector(lockManager); assertTrue(deadlockDetector.victims().isEmpty()); }
@Test public void testDeadlockOf2() throws Exception { TestKey k0 = key(0); TestKey k1 = key(1); a.lock(k0); b.lock(k1); a.lock(k1); b.lock(k0); DeadlockDetector deadlockDetector = new DeadlockDetector(lockManager); Set<Transaction> victims = deadlockDetector.victims(); assertEquals(1, victims.size()); assertEquals(latestStart(a, b).transaction(), victims.iterator().next()); }
@Test public void testDeadlockOf3() throws Exception { TestKey k0 = key(0); TestKey k1 = key(1); TestKey k2 = key(2); a.lock(k0); b.lock(k1); c.lock(k2); a.lock(k1); b.lock(k2); c.lock(k0); DeadlockDetector deadlockDetector = new DeadlockDetector(lockManager); Set<Transaction> victims = deadlockDetector.victims(); assertEquals(1, victims.size()); assertEquals(latestStart(a, b, c).transaction(), victims.iterator().next()); }
@Test public void testDeadlockWithPileup() throws Exception { TestKey k1 = key(1); TestKey k2 = key(2); b.lock(k1); c.lock(k2); b.lock(k2); c.lock(k1); a.lock(k1); DeadlockDetector deadlockDetector = new DeadlockDetector(lockManager); Set<Transaction> victims = deadlockDetector.victims(); assertEquals(1, victims.size()); assertEquals(latestStart(b, c).transaction(), victims.iterator().next()); }
@Test public void testTwoDeadlocks() throws Exception { TestKey k0 = key(0); TestKey k1 = key(1); TestKey k2 = key(2); TestKey k3 = key(3); a.lock(k0); b.lock(k1); a.lock(k1); b.lock(k0); c.lock(k2); d.lock(k3); c.lock(k3); d.lock(k2); DeadlockDetector deadlockDetector = new DeadlockDetector(lockManager); Set<Transaction> victims = deadlockDetector.victims(); int count = 0; for (Transaction victim : victims) { if (victim == latestStart(a, b).transaction() || victim == latestStart(c, d).transaction()) { count++; } else { fail(); } } assertEquals(2, count); }