com.bigdata.concurrent

Class TestTxDag

java.lang.Object

junit.framework.Assert

junit.framework.TestCase

com.bigdata.concurrent.TestTxDag

All Implemented Interfaces:

junit.framework.Test

public class TestTxDag
extends junit.framework.TestCase

Test suite for online transaction deadlock algorithm.

Version:

$Id$

Author:

Bryan Thompson

Field Summary

Fields

Modifier and Type	Field and Description
static org.apache.log4j.Logger	log

Constructor Summary

Constructors

Constructor and Description
TestTxDag()
TestTxDag(String name)

Method Summary

Methods

Modifier and Type	Method and Description
void	assertSameEdges(TxDag.Edge[] expected, TxDag.Edge[] actual) Compares two Edge[]s and verifies that the same edges are defined without regard to order.
void	assertSamePathCounts(int[][] expected, int[][] actual) Compares two path count matrices for equality.
void	assertSameValues(int[] expected, int[] actual) Verifies that actual contains all of the same values as expected in the same order.
void	assertSameValuesAnyOrder(int[] expected, int[] actual) Verifies that actual contains all of the same values as expected without regard to order.
void	doSymmetricOperationsTest(Random r, TxDag dag) Implements the performance test for testSymmetricOperations().
void	test_addEdge_001() Simple tests of TxDag.addEdge(Object, Object), TxDag.hasEdge(Object, Object)and friends.
void	test_addEdge_correctRejection_001() Test for correct rejection of addEdge() when edge already exists.
void	test_addEdge_correctRejection_002() Test for correct rejection of addEdge() when either parameter is null or when both parameters are the same.
void	test_addEdges_correctRejection_001() Test for correct rejection of addEdges() when an edge already exists.
void	test_addEdges_correctRejection_002() Test for correct rejection of addEdge() when either parameter is null, when one of the targets is null, or when one of the targets is given more than once.
void	test_capacity_001() Test capacity limits.
void	test_ctor() Constructor tests.
void	test_deadlock_001() The first in a series of simple tests which verify that the DAG is correctly detecting updates when a set of new edges would result in a cycle.
void	test_deadlock_002()
void	test_deadlock_003()
void	test_deadlock_batch_001()
void	test_getOrder_001() Verify that TxDag.lookup(Object, boolean) does not cause TxDag.getOrder() to include the new vertex until an edge has been asserted for that vertex.
void	test_lookup_001() Test ability to generate unique transaction identifier used by TxDagto index into its internal arrays.
void	test_lookup_002() Correct rejection test when transaction object is null.
void	test_noCycles__batch_001() Verify that the DAG state is correctly updated when adding a variety of WAITS_FOR relationships that do NOT form cycles (using the batch operation to add edges).
void	test_noCycles_001() Verify that the DAG state is correctly updated when adding a variety of WAITS_FOR relationships that do NOT form cycles.
void	test_recyclingIndices() Verify that we can recycle the internal transaction identifiers when a transaction is removed from the DAG (either through abort or commit actions).
void	test_updateClosure_001() Tests of the update to the internal matrix M[u,v].
void	test_updateClosure_002() A sequence of tests of the internal state of the TxDag with a capacity of 4 after adding an edge.
void	testAssertSameEdges() Some tests to verify #assertSameEdges(Edge[], Edge[]).
void	testSymmetricOperations() Test adds N random edges to the graph and then removes them and verifies that removal correctly reproduces each intermediate state following an edge addition.

Methods inherited from class junit.framework.TestCase

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

log

public static final org.apache.log4j.Logger log

Constructor Detail

TestTxDag

public TestTxDag()

TestTxDag

public TestTxDag(String name)

Method Detail

test_ctor

public void test_ctor()

Constructor tests.

test_lookup_001

public void test_lookup_001()

Test ability to generate unique transaction identifier used by TxDagto index into its internal arrays. This test verifies that insert is conditional, that lookup fails if tx was not registered, and that we can insert and then lookup a transaction in the DAG. The test also verifies that the TxDag.size()updates as vertices are added to the graph and does not update when the vertex already exists in the graph.

test_lookup_002

public void test_lookup_002()

Correct rejection test when transaction object is null.

test_capacity_001

public void test_capacity_001()

Test capacity limits. This test verifies that insert fails if capacity the graph (the maximum #of vertices) would be exceeded.

test_addEdge_001

public void test_addEdge_001()

Simple tests of TxDag.addEdge(Object, Object), TxDag.hasEdge(Object, Object)and friends.

test_addEdge_correctRejection_001

public void test_addEdge_correctRejection_001()

Test for correct rejection of addEdge() when edge already exists.

test_addEdge_correctRejection_002

public void test_addEdge_correctRejection_002()

Test for correct rejection of addEdge() when either parameter is null or when both parameters are the same.

test_addEdges_correctRejection_001

public void test_addEdges_correctRejection_001()

Test for correct rejection of addEdges() when an edge already exists.

test_addEdges_correctRejection_002

public void test_addEdges_correctRejection_002()

Test for correct rejection of addEdge() when either parameter is null, when one of the targets is null, or when one of the targets is given more than once.

test_getOrder_001

public void test_getOrder_001()

Verify that TxDag.lookup(Object, boolean) does not cause TxDag.getOrder() to include the new vertex until an edge has been asserted for that vertex.

This also tests TxDag.getOrder(int t, int u), which is similar to TxDag.getOrder() but it always includes the specified vertices in the returned int[].

See Also:

TxDag.lookup(Object, boolean), TxDag.getOrder()

assertSameValues

public void assertSameValues(int[] expected,
                    int[] actual)

Verifies that actual contains all of the same values as expected in the same order.

Parameters:

expected - An integer array.

actual - Another integer array.

assertSameValuesAnyOrder

public void assertSameValuesAnyOrder(int[] expected,
                            int[] actual)

Verifies that actual contains all of the same values as expected without regard to order.

Parameters:

expected - An integer array.

actual - Another integer array.

test_updateClosure_001

public void test_updateClosure_001()

Tests of the update to the internal matrix M[u,v]. This matrix maintains the #of distinct paths from u to v based on the edges in the directed graph, W.

Note: These tests are written directly using the TxDag.updateClosure(int, int, boolean) method, so the matrix W is not actually updated.

test_updateClosure_002

public void test_updateClosure_002()

A sequence of tests of the internal state of the TxDag with a capacity of 4 after adding an edge.

doSymmetricOperationsTest

public void doSymmetricOperationsTest(Random r,
                             TxDag dag)

Implements the performance test for testSymmetricOperations().

Performs random additive operations on the DAG until a deadlock results. The initial state and the state after each additive operation is stored. Once a deadlock is reached, verifies that the last stored state is still valid (deadlock should not update the state of the DAG) and then performs the inverse of each of the addition operations in the reverse order in which they were applied. After each inverse operation, verifies that the state of the DAG corresponds to the state before the corresponding additive operation.

The additive operations and their inverses are:

• insert/remove vertex
• insert/remove edge

A vertex corresponds to a transaction. Creating a vertex therefore corresponds to the action of starting a new transaction. Likewise removing a vertex corresponds to the action of terminating a transaction (either by aborting the transaction or committing the transaction).

Parameters:

r - A random number generator.

dag - A dag with a maximum capacity.

assertSamePathCounts

public void assertSamePathCounts(int[][] expected,
                        int[][] actual)

Compares two path count matrices for equality.

Parameters:

expected - An int[][] matrix with at least two rows and two columns.

actual - Another int[][] matrix with the same dimensions.

assertSameEdges

public void assertSameEdges(TxDag.Edge[] expected,
                   TxDag.Edge[] actual)

Compares two Edge[]s and verifies that the same edges are defined without regard to order.

Parameters:

expected - The expected Edge[].

actual - The actual Edge[].

testAssertSameEdges

public void testAssertSameEdges()

Some tests to verify #assertSameEdges(Edge[], Edge[]).

test_recyclingIndices

public void test_recyclingIndices()

Verify that we can recycle the internal transaction identifiers when a transaction is removed from the DAG (either through abort or commit actions).

Transaction objects are application defined. They are mapped into indices for the internal arrays by TxDag.lookup(Object, boolean). Those indices must be released for reuse by TxDag.releaseVertex(Object) of the capacity of the graph will be exhausted. This test verifies that they are.

The test creates and removes vertices repeatedly and verifies that we can create more vertices than would be allowed for by the capacity (therefore suggesting that vertices are being recycled correctly).

test_noCycles_001

public void test_noCycles_001()

Verify that the DAG state is correctly updated when adding a variety of WAITS_FOR relationships that do NOT form cycles.

test_noCycles__batch_001

public void test_noCycles__batch_001()

Verify that the DAG state is correctly updated when adding a variety of WAITS_FOR relationships that do NOT form cycles (using the batch operation to add edges).

test_deadlock_001

public void test_deadlock_001()

The first in a series of simple tests which verify that the DAG is correctly detecting updates when a set of new edges would result in a cycle.

test_deadlock_002

public void test_deadlock_002()

test_deadlock_003

public void test_deadlock_003()

test_deadlock_batch_001

public void test_deadlock_batch_001()

testSymmetricOperations

public void testSymmetricOperations()

Test adds N random edges to the graph and then removes them and verifies that removal correctly reproduces each intermediate state following an edge addition. Edges are added until a deadlock results. We verify that the deadlock did not update the internal matrix M and then backup state by state removing each edge in the reverse order and verifying that the correct state is reproduced as the edge is removed.

Note: This test uses "small" matrices (20 vertices) to keep the memory footprint down since it makes a copy of the state of the DAG after each action. As the capacity of the graph goes up, this test will begin to stress the garbage collector so more trials and moderate capacity makes more sense.

See Also:

doSymmetricOperationsTest(Random, TxDag)