| /******************************************************************************* |
| * Copyright (c) 2003, 2012 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * IBM - Initial API and implementation |
| *******************************************************************************/ |
| package org.eclipse.core.tests.runtime.jobs; |
| |
| import java.util.*; |
| import junit.framework.*; |
| import org.eclipse.core.internal.jobs.*; |
| import org.eclipse.core.runtime.*; |
| import org.eclipse.core.runtime.jobs.*; |
| import org.eclipse.core.tests.harness.FussyProgressMonitor; |
| import org.eclipse.core.tests.harness.TestBarrier; |
| |
| /** |
| * Tests implementation of ILock objects |
| */ |
| public class DeadlockDetectionTest extends TestCase { |
| private final IJobManager manager = Job.getJobManager(); |
| |
| public DeadlockDetectionTest() { |
| super(null); |
| } |
| |
| public DeadlockDetectionTest(String name) { |
| super(name); |
| } |
| |
| public static Test suite() { |
| return new TestSuite(DeadlockDetectionTest.class); |
| // TestSuite suite = new TestSuite(); |
| // suite.addTest(new DeadlockDetectionTest("testImplicitRules")); |
| // return suite; |
| } |
| |
| /** |
| * Creates n runnables on the given lock and adds them to the given list. |
| */ |
| private void createRunnables(ILock[] locks, int n, ArrayList allRunnables, boolean cond) { |
| for (int i = 0; i < n; i++) { |
| allRunnables.add(new RandomTestRunnable(locks, "# " + (allRunnables.size() + 1), cond)); |
| try { |
| Thread.sleep(10); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| } |
| } |
| |
| private LockManager getLockManager() { |
| return ((JobManager) manager).getLockManager(); |
| } |
| |
| /** |
| * Asks all threads to stop executing |
| */ |
| private void kill(ArrayList allRunnables) { |
| for (Iterator it = allRunnables.iterator(); it.hasNext();) { |
| RandomTestRunnable r = (RandomTestRunnable) it.next(); |
| r.kill(); |
| } |
| } |
| |
| /** |
| * Test that deadlock between locks is detected and resolved. |
| * Test with 6 threads competing for 3 locks from a set of 6. |
| */ |
| public void testComplex() { |
| ArrayList allRunnables = new ArrayList(); |
| LockManager lockManager = new LockManager(); |
| OrderedLock lock1 = lockManager.newLock(); |
| OrderedLock lock2 = lockManager.newLock(); |
| OrderedLock lock3 = lockManager.newLock(); |
| OrderedLock lock4 = lockManager.newLock(); |
| OrderedLock lock5 = lockManager.newLock(); |
| OrderedLock lock6 = lockManager.newLock(); |
| createRunnables(new ILock[] {lock1, lock2, lock3}, 1, allRunnables, true); |
| createRunnables(new ILock[] {lock2, lock3, lock4}, 1, allRunnables, true); |
| createRunnables(new ILock[] {lock3, lock4, lock5}, 1, allRunnables, true); |
| createRunnables(new ILock[] {lock4, lock5, lock6}, 1, allRunnables, true); |
| createRunnables(new ILock[] {lock5, lock6, lock1}, 1, allRunnables, true); |
| createRunnables(new ILock[] {lock6, lock1, lock2}, 1, allRunnables, true); |
| start(allRunnables); |
| try { |
| Thread.sleep(5000); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| kill(allRunnables); |
| |
| for (int i = 0; i < allRunnables.size(); i++) { |
| try { |
| ((Thread) allRunnables.get(i)).join(100000); |
| } catch (InterruptedException e1) { |
| //ignore |
| } |
| assertTrue("1." + i, !((Thread) allRunnables.get(i)).isAlive()); |
| } |
| //the underlying array has to be empty |
| assertTrue("Locks not removed from graph.", lockManager.isEmpty()); |
| } |
| |
| /** |
| * Test simplest deadlock case (2 threads, 2 locks). |
| */ |
| public void testSimpleDeadlock() { |
| ArrayList allRunnables = new ArrayList(); |
| LockManager localManager = new LockManager(); |
| OrderedLock lock1 = localManager.newLock(); |
| OrderedLock lock2 = localManager.newLock(); |
| |
| createRunnables(new ILock[] {lock1, lock2}, 1, allRunnables, false); |
| createRunnables(new ILock[] {lock2, lock1}, 1, allRunnables, false); |
| |
| start(allRunnables); |
| try { |
| Thread.sleep(1000); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| kill(allRunnables); |
| |
| for (int i = 0; i < allRunnables.size(); i++) { |
| try { |
| ((Thread) allRunnables.get(i)).join(100000); |
| } catch (InterruptedException e1) { |
| //ignore |
| } |
| assertTrue("1." + i, !((Thread) allRunnables.get(i)).isAlive()); |
| } |
| //the underlying array has to be empty |
| assertTrue("Locks not removed from graph.", localManager.isEmpty()); |
| } |
| |
| /** |
| * Test a more complicated scenario with 3 threads and 3 locks. |
| */ |
| public void testThreeLocks() { |
| ArrayList allRunnables = new ArrayList(); |
| LockManager lockManager = new LockManager(); |
| OrderedLock lock1 = lockManager.newLock(); |
| OrderedLock lock2 = lockManager.newLock(); |
| OrderedLock lock3 = lockManager.newLock(); |
| |
| createRunnables(new ILock[] {lock1, lock2}, 1, allRunnables, false); |
| createRunnables(new ILock[] {lock2, lock3}, 1, allRunnables, false); |
| createRunnables(new ILock[] {lock3, lock1}, 1, allRunnables, false); |
| |
| start(allRunnables); |
| try { |
| Thread.sleep(2000); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| kill(allRunnables); |
| |
| for (int i = 0; i < allRunnables.size(); i++) { |
| try { |
| ((Thread) allRunnables.get(i)).join(100000); |
| } catch (InterruptedException e1) { |
| //ignore |
| } |
| assertTrue("1." + i, !((Thread) allRunnables.get(i)).isAlive()); |
| } |
| //the underlying array has to be empty |
| assertTrue("Locks not removed from graph.", lockManager.isEmpty()); |
| } |
| |
| /** |
| * Test simple deadlock with 2 threads trying to get 1 rule and 1 lock. |
| */ |
| public void testRuleLockInteraction() { |
| final ILock lock = manager.newLock(); |
| final ISchedulingRule rule = new IdentityRule(); |
| final int[] status = {TestBarrier.STATUS_WAIT_FOR_START, TestBarrier.STATUS_WAIT_FOR_START}; |
| |
| Thread first = new Thread("Test1") { |
| public void run() { |
| lock.acquire(); |
| status[0] = TestBarrier.STATUS_START; |
| assertTrue("1.0", getLockManager().isLockOwner()); |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.beginRule(rule, null); |
| assertTrue("2.0", getLockManager().isLockOwner()); |
| manager.endRule(rule); |
| lock.release(); |
| status[0] = TestBarrier.STATUS_DONE; |
| } |
| }; |
| |
| Thread second = new Thread("Test2") { |
| public void run() { |
| manager.beginRule(rule, null); |
| status[1] = TestBarrier.STATUS_START; |
| assertTrue("1.0", getLockManager().isLockOwner()); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| lock.acquire(); |
| assertTrue("2.0", getLockManager().isLockOwner()); |
| lock.release(); |
| manager.endRule(rule); |
| status[1] = TestBarrier.STATUS_DONE; |
| } |
| }; |
| |
| first.start(); |
| second.start(); |
| |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_START); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| |
| status[0] = TestBarrier.STATUS_RUNNING; |
| status[1] = TestBarrier.STATUS_RUNNING; |
| |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_DONE); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_DONE); |
| waitForThreadDeath(first); |
| waitForThreadDeath(second); |
| assertTrue("3.0", !first.isAlive()); |
| assertTrue("4.0", !second.isAlive()); |
| //the underlying array has to be empty |
| if (!getLockManager().isEmpty()) |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test the interaction between jobs with rules and the acquisition of locks. |
| */ |
| public void testJobRuleLockInteraction() { |
| final int[] status = {TestBarrier.STATUS_WAIT_FOR_START, TestBarrier.STATUS_WAIT_FOR_START}; |
| final ISchedulingRule rule1 = new IdentityRule(); |
| final ISchedulingRule rule2 = new IdentityRule(); |
| final ILock lock = manager.newLock(); |
| |
| Job first = new Job("Test1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| assertTrue("1.0", getLockManager().isLockOwner()); |
| monitor.beginTask("Testing", 1); |
| status[0] = TestBarrier.STATUS_START; |
| lock.acquire(); |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| assertTrue("2.0", getLockManager().isLockOwner()); |
| lock.release(); |
| monitor.worked(1); |
| status[0] = TestBarrier.STATUS_DONE; |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| Job second = new Job("Test2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| assertTrue("1.0", getLockManager().isLockOwner()); |
| monitor.beginTask("Testing", 1); |
| status[1] = TestBarrier.STATUS_START; |
| lock.acquire(); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| assertTrue("2.0", getLockManager().isLockOwner()); |
| lock.release(); |
| monitor.worked(1); |
| status[1] = TestBarrier.STATUS_DONE; |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| first.setRule(rule1); |
| second.setRule(rule2); |
| first.schedule(); |
| second.schedule(); |
| |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_START); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| |
| status[0] = TestBarrier.STATUS_RUNNING; |
| status[1] = TestBarrier.STATUS_RUNNING; |
| |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_DONE); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_DONE); |
| waitForCompletion(first); |
| waitForCompletion(second); |
| |
| assertEquals("3.0", Job.NONE, first.getState()); |
| assertEquals("3.1", Status.OK_STATUS, first.getResult()); |
| assertEquals("4.0", Job.NONE, second.getState()); |
| assertEquals("4.1", Status.OK_STATUS, second.getResult()); |
| //the underlying array has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Regression test for bug 46894. Stale entries left over in graph. |
| */ |
| public void testRuleHierarchyWaitReplace() { |
| final int NUM_JOBS = 3; |
| final int[] status = new int[NUM_JOBS]; |
| Arrays.fill(status, TestBarrier.STATUS_WAIT_FOR_START); |
| final ISchedulingRule[] rules = {new PathRule("/testRuleHierarchyWaitReplace"), new PathRule("/testRuleHierarchyWaitReplace/B"), new PathRule("/testRuleHierarchyWaitReplace/C")}; |
| final ILock[] locks = {manager.newLock(), manager.newLock()}; |
| Job[] jobs = new Job[NUM_JOBS]; |
| |
| jobs[0] = new Job("Test 0") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| manager.beginRule(rules[0], null); |
| status[0] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[0]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[1] = new Job("Test 1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| locks[0].acquire(); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| manager.beginRule(rules[1], new TestBlockingMonitor(status, 1)); |
| status[1] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| locks[1].acquire(); |
| locks[1].release(); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[1]); |
| locks[0].release(); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[2] = new Job("Test 2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| locks[1].acquire(); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_START); |
| manager.beginRule(rules[2], new TestBlockingMonitor(status, 2)); |
| status[2] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[2]); |
| locks[1].release(); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| jobs[i].schedule(); |
| } |
| //wait until the first job starts |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //now let the second job start |
| status[1] = TestBarrier.STATUS_START; |
| //wait until it blocks on the beginRule call |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_BLOCKED); |
| |
| //let the third job start, and wait until it too blocks |
| status[2] = TestBarrier.STATUS_START; |
| //wait until it blocks on the beginRule call |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_BLOCKED); |
| |
| //end the first job |
| status[0] = TestBarrier.STATUS_RUNNING; |
| |
| //wait until the second job gets the rule |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //let the job finish |
| status[1] = TestBarrier.STATUS_RUNNING; |
| |
| //now wait until the third job gets the rule |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //let the job finish |
| status[2] = TestBarrier.STATUS_RUNNING; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| waitForCompletion(jobs[i]); |
| } |
| |
| for (int i = 0; i < jobs.length; i++) { |
| assertEquals("10." + i, Job.NONE, jobs[i].getState()); |
| assertEquals("10." + i, Status.OK_STATUS, jobs[i].getResult()); |
| } |
| //the underlying graph has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Regression test for bug 46894. Deadlock was not detected (before). |
| */ |
| public void testDetectDeadlock() { |
| final int NUM_JOBS = 3; |
| final int[] status = new int[NUM_JOBS]; |
| Arrays.fill(status, TestBarrier.STATUS_WAIT_FOR_START); |
| final ISchedulingRule[] rules = {new PathRule("/testDetectDeadlock"), new PathRule("/testDetectDeadlock/B"), new PathRule("/testDetectDeadlock/C")}; |
| final ILock lock = manager.newLock(); |
| Job[] jobs = new Job[NUM_JOBS]; |
| |
| jobs[0] = new Job("Test 0") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| manager.beginRule(rules[1], null); |
| status[0] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[1]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[1] = new Job("Test 1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| lock.acquire(); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| manager.beginRule(rules[0], new TestBlockingMonitor(status, 1)); |
| status[1] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[0]); |
| lock.release(); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[2] = new Job("Test 2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_START); |
| manager.beginRule(rules[2], null); |
| status[2] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_RUNNING); |
| lock.acquire(); |
| lock.release(); |
| manager.endRule(rules[2]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| jobs[i].schedule(); |
| } |
| //wait until the first job starts |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //now let the third job start |
| status[2] = TestBarrier.STATUS_START; |
| //wait until it gets the rule |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_WAIT_FOR_RUN); |
| |
| //let the second job start |
| status[1] = TestBarrier.STATUS_START; |
| //wait until it blocks on the beginRule call |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_BLOCKED); |
| |
| //let the third job try for the lock |
| status[2] = TestBarrier.STATUS_RUNNING; |
| //end the first job |
| status[0] = TestBarrier.STATUS_RUNNING; |
| |
| //wait until the second job gets the rule |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //let the job finish |
| status[1] = TestBarrier.STATUS_RUNNING; |
| //wait until all jobs are done |
| for (int i = 0; i < jobs.length; i++) { |
| waitForCompletion(jobs[i]); |
| } |
| |
| for (int i = 0; i < jobs.length; i++) { |
| assertEquals("10." + i, Job.NONE, jobs[i].getState()); |
| assertEquals("10." + i, Status.OK_STATUS, jobs[i].getResult()); |
| } |
| //the underlying graph has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test that when 3 columns and 1 row are empty, they are correctly removed from the graph. |
| */ |
| public void testMultipleColumnRemoval() { |
| final int NUM_JOBS = 3; |
| final int[] status = new int[NUM_JOBS]; |
| Arrays.fill(status, TestBarrier.STATUS_WAIT_FOR_START); |
| final ISchedulingRule[] rules = {new PathRule("/testMultipleColumnRemoval"), new PathRule("/testMultipleColumnRemoval/B"), new PathRule("/testMultipleColumnRemoval/C")}; |
| final IProgressMonitor first = new TestBlockingMonitor(status, 1); |
| final IProgressMonitor second = new TestBlockingMonitor(status, 2); |
| Job[] jobs = new Job[NUM_JOBS]; |
| |
| jobs[0] = new Job("Test 0") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| manager.beginRule(rules[0], null); |
| status[0] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[0]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[1] = new Job("Test 1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| manager.beginRule(rules[1], first); |
| monitor.worked(1); |
| } finally { |
| status[1] = TestBarrier.STATUS_DONE; |
| manager.endRule(rules[1]); |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[2] = new Job("Test 2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_START); |
| manager.beginRule(rules[2], second); |
| monitor.worked(1); |
| } finally { |
| status[2] = TestBarrier.STATUS_DONE; |
| manager.endRule(rules[2]); |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| //schedule all the jobs |
| for (int i = 0; i < jobs.length; i++) { |
| jobs[i].schedule(); |
| } |
| //wait until the first job starts |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //now let the other two jobs start |
| status[1] = TestBarrier.STATUS_START; |
| status[2] = TestBarrier.STATUS_START; |
| //wait until both are blocked on the beginRule call |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_BLOCKED); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_BLOCKED); |
| |
| //cancel the blocked jobs |
| first.setCanceled(true); |
| second.setCanceled(true); |
| |
| //wait until both jobs are done |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_DONE); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_DONE); |
| |
| //end the first job |
| status[0] = TestBarrier.STATUS_RUNNING; |
| //wait until all jobs are done |
| for (int i = 0; i < jobs.length; i++) { |
| waitForCompletion(jobs[i]); |
| } |
| |
| //the underlying graph has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test that the graph is cleared after a thread stops waiting for a rule. |
| */ |
| public void testBeginRuleCancelAfterWait() { |
| final ISchedulingRule rule1 = new PathRule("/testBeginRuleCancelAfterWait"); |
| final ISchedulingRule rule2 = new PathRule("/testBeginRuleCancelAfterWait/B"); |
| |
| final int[] status = {TestBarrier.STATUS_WAIT_FOR_START, TestBarrier.STATUS_WAIT_FOR_START}; |
| final IProgressMonitor canceller = new FussyProgressMonitor(); |
| |
| Job ruleOwner = new Job("Test1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| status[0] = TestBarrier.STATUS_START; |
| manager.beginRule(rule1, null); |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rule1); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| status[0] = TestBarrier.STATUS_DONE; |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| Job ruleWait = new Job("Test2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| status[1] = TestBarrier.STATUS_RUNNING; |
| manager.beginRule(rule2, canceller); |
| monitor.worked(1); |
| } finally { |
| manager.endRule(rule2); |
| monitor.done(); |
| status[1] = TestBarrier.STATUS_DONE; |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| ruleOwner.schedule(); |
| TestBarrier.waitForStatus(status, TestBarrier.STATUS_START); |
| |
| //schedule a job that is going to begin a conflicting rule and then cancel the wait |
| ruleWait.schedule(); |
| try { |
| Thread.sleep(100); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| //cancel the wait for the rule |
| canceller.setCanceled(true); |
| //wait until the job completes |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_DONE); |
| |
| //let the first job finish |
| status[0] = TestBarrier.STATUS_RUNNING; |
| TestBarrier.waitForStatus(status, TestBarrier.STATUS_DONE); |
| waitForCompletion(ruleOwner); |
| //the underlying graph should now be empty |
| assertTrue("Canceled rule not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test that implicit rules do not create extraneous entries |
| */ |
| public void testImplicitRules() { |
| final int NUM_JOBS = 4; |
| final int[] status = new int[NUM_JOBS]; |
| Arrays.fill(status, TestBarrier.STATUS_WAIT_FOR_START); |
| final ISchedulingRule[] rules = {new PathRule("/testImplicitRules"), new PathRule("/testImplicitRules/B"), new PathRule("/testImplicitRules/C"), new PathRule("/testImplicitRules/B/D")}; |
| Job[] jobs = new Job[NUM_JOBS]; |
| |
| jobs[0] = new Job("Test 0") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| manager.beginRule(rules[3], null); |
| status[0] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[3]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[1] = new Job("Test 1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| manager.beginRule(rules[2], null); |
| status[1] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[2]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[2] = new Job("Test 2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_START); |
| manager.beginRule(rules[0], new TestBlockingMonitor(status, 2)); |
| status[2] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[0]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[3] = new Job("Test 3") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_START); |
| manager.beginRule(rules[1], new TestBlockingMonitor(status, 3)); |
| status[3] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[1]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| jobs[i].schedule(); |
| } |
| //wait until the first 2 jobs start |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_WAIT_FOR_RUN); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //now let the third job start |
| status[2] = TestBarrier.STATUS_START; |
| //wait until it blocks on the beginRule call |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_BLOCKED); |
| |
| //let the fourth job start |
| status[3] = TestBarrier.STATUS_START; |
| //wait until it blocks on the beginRule call |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_BLOCKED); |
| |
| //end the first 2 jobs |
| status[0] = TestBarrier.STATUS_RUNNING; |
| status[1] = TestBarrier.STATUS_RUNNING; |
| |
| //the third and fourth jobs will now compete in non-deterministic order |
| int runningCount = 0; |
| long waitStart = System.currentTimeMillis(); |
| while (runningCount < 2) { |
| if (status[2] == TestBarrier.STATUS_WAIT_FOR_RUN) { |
| //the third job got the rule - let it finish |
| runningCount++; |
| status[2] = TestBarrier.STATUS_RUNNING; |
| } |
| if (status[3] == TestBarrier.STATUS_WAIT_FOR_RUN) { |
| //the fourth job got the rule - let it finish |
| runningCount++; |
| status[3] = TestBarrier.STATUS_RUNNING; |
| } |
| //timeout if the two jobs don't start within a reasonable time |
| long elapsed = System.currentTimeMillis() - waitStart; |
| assertTrue("Timeout waiting for job to end: " + elapsed, elapsed < 30000); |
| } |
| //wait until all jobs are done |
| for (int i = 0; i < jobs.length; i++) |
| waitForCompletion(jobs[i]); |
| |
| for (int i = 0; i < jobs.length; i++) { |
| assertEquals("10." + i, Job.NONE, jobs[i].getState()); |
| assertEquals("10." + i, Status.OK_STATUS, jobs[i].getResult()); |
| } |
| //the underlying graph has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Regression test for bug 46894. Stale rules left over in graph. |
| */ |
| public void _testRuleHierarchyLockInteraction() { |
| final int NUM_JOBS = 5; |
| final int[] status = new int[NUM_JOBS]; |
| Arrays.fill(status, TestBarrier.STATUS_WAIT_FOR_START); |
| final ISchedulingRule[] rules = {new PathRule("/A"), new PathRule("/A/B"), new PathRule("/A/C")}; |
| Job[] jobs = new Job[NUM_JOBS]; |
| |
| jobs[0] = new Job("Test 0") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| manager.beginRule(rules[1], null); |
| status[0] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[1]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[1] = new Job("Test 1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| manager.beginRule(rules[2], null); |
| status[1] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[2]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[2] = new Job("Test 2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_START); |
| manager.beginRule(rules[0], new TestBlockingMonitor(status, 2)); |
| status[2] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[0]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[3] = new Job("Test 3") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_START); |
| manager.beginRule(rules[2], new TestBlockingMonitor(status, 3)); |
| status[3] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[2]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| jobs[4] = new Job("Test 4") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", 1); |
| TestBarrier.waitForStatus(status, 4, TestBarrier.STATUS_START); |
| manager.beginRule(rules[2], new TestBlockingMonitor(status, 4)); |
| status[4] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 4, TestBarrier.STATUS_RUNNING); |
| manager.endRule(rules[2]); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| jobs[i].schedule(); |
| } |
| //wait until the first job starts |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //now let the second job start |
| status[1] = TestBarrier.STATUS_START; |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_WAIT_FOR_RUN); |
| |
| //let the third job register the wait |
| status[2] = TestBarrier.STATUS_START; |
| //wait until the job is blocked on the scheduling rule |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_BLOCKED); |
| |
| //let the fourth job register the wait |
| status[3] = TestBarrier.STATUS_START; |
| //wait until the job is blocked on the scheduling rule |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_BLOCKED); |
| |
| //end the first job, and the second job |
| status[0] = TestBarrier.STATUS_RUNNING; |
| status[1] = TestBarrier.STATUS_RUNNING; |
| |
| //wait until the third job gets the rule |
| TestBarrier.waitForStatus(status, 2, TestBarrier.STATUS_WAIT_FOR_RUN); |
| |
| //let the fifth job start its wait |
| status[4] = TestBarrier.STATUS_START; |
| TestBarrier.waitForStatus(status, 4, TestBarrier.STATUS_BLOCKED); |
| |
| //let the third job finish |
| status[2] = TestBarrier.STATUS_RUNNING; |
| |
| //wait until the fourth job gets the rule |
| TestBarrier.waitForStatus(status, 3, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //let the fourth job end |
| status[3] = TestBarrier.STATUS_RUNNING; |
| |
| //wait until the fifth job gets the rule |
| TestBarrier.waitForStatus(status, 4, TestBarrier.STATUS_WAIT_FOR_RUN); |
| //let the fifth job end |
| status[4] = TestBarrier.STATUS_RUNNING; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| waitForCompletion(jobs[i]); |
| } |
| |
| for (int i = 0; i < jobs.length; i++) { |
| assertEquals("10." + i, Job.NONE, jobs[i].getState()); |
| assertEquals("10." + i, Status.OK_STATUS, jobs[i].getResult()); |
| } |
| //the underlying graph has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test that the deadlock detector resolves deadlock correctly. |
| * 60 threads are competing for 6 locks (need to acquire 3 locks at the same time). |
| */ |
| public void testVeryComplex() { |
| ArrayList allRunnables = new ArrayList(); |
| LockManager lockManager = new LockManager(); |
| OrderedLock lock1 = lockManager.newLock(); |
| OrderedLock lock2 = lockManager.newLock(); |
| OrderedLock lock3 = lockManager.newLock(); |
| OrderedLock lock4 = lockManager.newLock(); |
| OrderedLock lock5 = lockManager.newLock(); |
| OrderedLock lock6 = lockManager.newLock(); |
| createRunnables(new ILock[] {lock1, lock2, lock3}, 10, allRunnables, true); |
| createRunnables(new ILock[] {lock2, lock3, lock4}, 10, allRunnables, true); |
| createRunnables(new ILock[] {lock3, lock4, lock5}, 10, allRunnables, true); |
| createRunnables(new ILock[] {lock4, lock5, lock6}, 10, allRunnables, true); |
| createRunnables(new ILock[] {lock5, lock6, lock1}, 10, allRunnables, true); |
| createRunnables(new ILock[] {lock6, lock1, lock2}, 10, allRunnables, true); |
| start(allRunnables); |
| try { |
| Thread.sleep(5000); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| kill(allRunnables); |
| |
| for (int i = 0; i < allRunnables.size(); i++) { |
| try { |
| ((Thread) allRunnables.get(i)).join(100000); |
| } catch (InterruptedException e1) { |
| //ignore |
| } |
| assertTrue("1." + i, !((Thread) allRunnables.get(i)).isAlive()); |
| } |
| //the underlying array has to be empty |
| assertTrue("Locks not removed from graph.", lockManager.isEmpty()); |
| } |
| |
| /** |
| * Spin until the given job completes |
| */ |
| private void waitForCompletion(Job job) { |
| int i = 0; |
| while (job.getState() != Job.NONE) { |
| try { |
| Thread.sleep(100); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| assertTrue("Timeout waiting for job to end:" + job, ++i < 100); |
| } |
| } |
| |
| /** |
| * Spin until the given thread dies |
| */ |
| private void waitForThreadDeath(Thread thread) { |
| int i = 0; |
| while (thread.isAlive()) { |
| try { |
| Thread.sleep(100); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| assertTrue("Timeout waiting for job to end.", ++i < 100); |
| } |
| } |
| |
| /** |
| * Test a complex scenario of interaction between rules and locks. |
| * 15 jobs are competing for 5 rules and 5 locks. |
| * Each job must acquire 1 rule and 2 locks in random order. |
| */ |
| public void _testComplexRuleLockInteraction() { |
| final int NUM_LOCKS = 5; |
| final int[] status = {TestBarrier.STATUS_WAIT_FOR_START}; |
| final ISchedulingRule[] rules = {new PathRule("/A"), new PathRule("/A/B"), new PathRule("/A/C"), new PathRule("/A/B/D"), new PathRule("/A/C/E")}; |
| final ILock[] locks = {manager.newLock(), manager.newLock(), manager.newLock(), manager.newLock(), manager.newLock()}; |
| Job[] jobs = new Job[NUM_LOCKS * 3]; |
| final Random random = new Random(); |
| |
| for (int i = 0; i < jobs.length; i++) { |
| jobs[i] = new Job("Test" + i) { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| monitor.beginTask("Testing", IProgressMonitor.UNKNOWN); |
| while (status[0] != TestBarrier.STATUS_DONE) { |
| int indexRule = random.nextInt(NUM_LOCKS); |
| int indexLock = random.nextInt(NUM_LOCKS); |
| int secondIndex = random.nextInt(NUM_LOCKS); |
| if ((indexRule % 2) == 0) { |
| manager.beginRule(rules[indexRule], null); |
| locks[indexLock].acquire(); |
| locks[secondIndex].acquire(); |
| assertTrue(indexRule + ".0", getLockManager().isLockOwner()); |
| locks[secondIndex].release(); |
| locks[indexLock].release(); |
| manager.endRule(rules[indexRule]); |
| } else { |
| locks[indexLock].acquire(); |
| manager.beginRule(rules[indexRule], null); |
| locks[secondIndex].acquire(); |
| assertTrue(indexLock + ".0", getLockManager().isLockOwner()); |
| locks[secondIndex].release(); |
| manager.endRule(rules[indexRule]); |
| locks[indexLock].release(); |
| } |
| monitor.worked(1); |
| } |
| } catch (RuntimeException e) { |
| e.printStackTrace(); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| jobs[i].schedule(); |
| } |
| |
| try { |
| Thread.sleep(5000); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| |
| status[0] = TestBarrier.STATUS_DONE; |
| |
| for (int i = 0; i < jobs.length; i++) { |
| int j = 0; |
| while (jobs[i].getState() != Job.NONE) { |
| try { |
| Thread.sleep(100); |
| } catch (InterruptedException e1) { |
| //ignore |
| } |
| //sanity check to avoid hanging tests |
| assertTrue("Timeout waiting for jobs to finish.", ++j < 1000); |
| } |
| } |
| |
| for (int i = 0; i < jobs.length; i++) { |
| assertEquals("10." + i, Job.NONE, jobs[i].getState()); |
| assertEquals("10." + i, Status.OK_STATUS, jobs[i].getResult()); |
| } |
| //the underlying array has to be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test that when a job with a rule is canceled, no stale entries are left in the graph. |
| */ |
| public void _testJobRuleCancellation() { |
| final ISchedulingRule rule = new IdentityRule(); |
| final int[] status = {TestBarrier.STATUS_WAIT_FOR_START}; |
| |
| Job first = new Job("Test1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| assertTrue("1.0", getLockManager().isLockOwner()); |
| status[0] = TestBarrier.STATUS_START; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_RUNNING); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| status[0] = TestBarrier.STATUS_DONE; |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| Job second = new Job("Test2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| assertTrue("2.0", getLockManager().isLockOwner()); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| first.setRule(rule); |
| second.setRule(rule); |
| |
| first.schedule(); |
| TestBarrier.waitForStatus(status, TestBarrier.STATUS_START); |
| |
| //schedule a job with the same rule and then cancel it |
| second.schedule(); |
| try { |
| Thread.sleep(100); |
| } catch (InterruptedException e) { |
| //ignore |
| } |
| second.cancel(); |
| status[0] = TestBarrier.STATUS_RUNNING; |
| TestBarrier.waitForStatus(status, TestBarrier.STATUS_DONE); |
| waitForCompletion(first); |
| //the underlying graph should now be empty |
| assertTrue("Canceled job not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| /** |
| * Test that a lock which was acquired several times and then suspended to resolve deadlock |
| * is set correctly to the proper depth when it is re-acquired by the thread that used to own it. |
| */ |
| public void _testLockMultipleAcquireThenSuspend() { |
| final ISchedulingRule rule = new IdentityRule(); |
| final ILock lock = manager.newLock(); |
| final int[] status = {TestBarrier.STATUS_WAIT_FOR_START, TestBarrier.STATUS_WAIT_FOR_START}; |
| |
| Job first = new Job("Test1") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| manager.beginRule(rule, null); |
| status[0] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_START); |
| lock.acquire(); |
| lock.release(); |
| manager.endRule(rule); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| |
| Job second = new Job("Test2") { |
| protected IStatus run(IProgressMonitor monitor) { |
| try { |
| lock.acquire(); |
| lock.acquire(); |
| lock.acquire(); |
| lock.acquire(); |
| status[1] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_START); |
| manager.beginRule(rule, null); |
| manager.endRule(rule); |
| lock.release(); |
| status[1] = TestBarrier.STATUS_WAIT_FOR_RUN; |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_RUNNING); |
| lock.release(); |
| lock.release(); |
| lock.release(); |
| monitor.worked(1); |
| } finally { |
| monitor.done(); |
| } |
| return Status.OK_STATUS; |
| } |
| }; |
| //schedule the jobs |
| first.schedule(); |
| second.schedule(); |
| //wait until one gets a rule, and the other acquires a lock |
| TestBarrier.waitForStatus(status, 0, TestBarrier.STATUS_WAIT_FOR_RUN); |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_WAIT_FOR_RUN); |
| |
| //let the deadlock happen |
| status[0] = TestBarrier.STATUS_START; |
| status[1] = TestBarrier.STATUS_START; |
| |
| //wait until it is resolved and the second job releases the lock once |
| TestBarrier.waitForStatus(status, 1, TestBarrier.STATUS_WAIT_FOR_RUN); |
| |
| //the underlying graph should not be empty yet |
| assertTrue("Held lock removed from graph.", !getLockManager().isEmpty()); |
| |
| //wait until the jobs are done |
| status[1] = TestBarrier.STATUS_RUNNING; |
| waitForCompletion(first); |
| waitForCompletion(second); |
| //the underlying graph should now be empty |
| assertTrue("Jobs not removed from graph.", getLockManager().isEmpty()); |
| } |
| |
| private void start(ArrayList allRunnables) { |
| for (Iterator it = allRunnables.iterator(); it.hasNext();) { |
| RandomTestRunnable r = (RandomTestRunnable) it.next(); |
| r.start(); |
| } |
| } |
| } |