[concurrency-interest] Bug in ConcurrentSkipListSet/ConcurrentSkipListMap?

Thorsten Möller Thorsten.Moeller at unibas.ch
Fri Dec 3 11:58:39 EST 2010


Hi all,

I believe I've found a bug in ConcurrentSkipListSet (or in
ConcurrentSkipListMap because the former is based on the latter). Since
I'm not 100% sure I thought I write to this list in order to cross check
and see if somebody here can reproduce the problem or tell me that I'm
missing something. The JUnit 4 test below (attachment) can be used to
reproduce the problem. It uses only Java classes. In short, the test
creates three threads which concurrently insert unique Long values into
a ConcurrentSkipListSet and check if they are contained in the set after
the insert. The test fails rarely in about 1 out of 10-15 runs (you
might need to run it often). If it fails the assertions in line 75 or 77
do not hold. If you run it often enough then you will also notice that
both test methods can fail, which means that it is not a matter of how
the Long values are created.

What I'm not 100% sure is whether the test is really written in a way
that it cannot create duplicated Long values. If not, then I think there
must be a bug in ConcurrentSkipListSet. Otherwise, I would like to know
why it can happen that duplicated Long values can be created. I also
tried to make sure that no auto(un)boxing is used and that the caching
implemented by Long is not used (by creating new instances using the
constructor Long(long)). Finally, since Long is immutable, there should
be no hashCode related problems.

Also interesting is that if I switch from a ConcurrentSkipListSet to a
synchronized TreeSet (by switching lines 40,41) the test always passes
(albeit it is slower which is an obvious result of the locking). This is
one more indication that there must be a bug in ConcurrentSkipListSet.

I could reproduce the bug using Oracle JDK 1.6.0_22 on both Windows XP
32bit and Linux 2.6.32-26 32bit machines.

Can anybody confirm the problem and do you agree that it must be a bug?

Thanks,
Thorsten





/*
* Created on 02.12.2010
*
*/
package ch.unibas.cs;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import org.junit.Test;
/**
*
* @author Thorsten Möller - Thorsten.Moeller at unibas.ch
*/
public class JavaTest
{
private static final int NUMBER_OF_ITERATIONS = 300000;
private static final int NUMBER_OF_THREADS = 3;
static final AtomicLong sequence = new AtomicLong(Long.MIN_VALUE);
static volatile long lsequence = Long.MIN_VALUE;
static final SortedSet<Long> values = new ConcurrentSkipListSet<Long>();
// static final SortedSet<Long> values =
Collections.synchronizedSortedSet(new TreeSet<Long>());
static final Lock lock = new ReentrantLock();
@Test
public final void testCreateTimestampLock() throws InterruptedException,
ExecutionException
{
final long initial = lsequence;
testRun(true);
assertEquals(lsequence, initial + NUMBER_OF_ITERATIONS *
NUMBER_OF_THREADS);
}
@Test
public final void testCreateTimestampAtomic() throws
InterruptedException, ExecutionException
{
final long initial = sequence.get();
testRun(false);
assertEquals(sequence.get(), initial + NUMBER_OF_ITERATIONS *
NUMBER_OF_THREADS);
}
private void testRun(final boolean locking) throws InterruptedException,
ExecutionException
{
final ExecutorService es =
Executors.newFixedThreadPool(NUMBER_OF_THREADS);
final List<Callable<Set<Long>>> tasks = new
ArrayList<Callable<Set<Long>>>();
for (int i = 0; i < NUMBER_OF_THREADS; i++)
{
tasks.add(new Callable<Set<Long>>() {
@Override public Set<Long> call() throws Exception
{
final Set<Long> seq = new LinkedHashSet<Long>();
Long value;
for (int j = 0; j < NUMBER_OF_ITERATIONS; j++)
{
value = (locking)? createViaLock() : createViaAtomicLong();
assertTrue(seq.add(value));
assertFalse(values.contains(value));
assertTrue(values.add(value));
assertTrue(values.contains(value));
assertTrue(values.remove(value));
assertFalse(values.contains(value));
}
return seq;
}
});
}
final List<Future<Set<Long>>> futures = es.invokeAll(tasks);
assertEquals(NUMBER_OF_THREADS, futures.size());
final List<Set<Long>> results = new
ArrayList<Set<Long>>(futures.size());
for (final Future<Set<Long>> future : futures)
{
results.add(future.get());
}
final Iterator<Set<Long>> it = results.iterator();
for (int i = 0; i < NUMBER_OF_THREADS && it.hasNext(); i++)
{
final Set<Long> result = it.next();
Long previous = null;
for (final Long l : result)
{
if (previous != null)
{
assertTrue(previous < l);
for (int j = i + 1; j < NUMBER_OF_THREADS; j++)
{
assertFalse(results.get(j).contains(l));
}
}
previous = l;
}
}
}
Long createViaLock()
{
lock.lock();
try
{
return new Long(lsequence++);
}
finally
{
lock.unlock();
}
}
Long createViaAtomicLong()
{
return new Long(sequence.getAndIncrement());
}
}
-------------- next part --------------
A non-text attachment was scrubbed...
Name: JavaTest.java
Type: application/octet-stream
Size: 3597 bytes
Desc: not available
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20101203/52a7638c/attachment.obj>


More information about the Concurrency-interest mailing list