[concurrency-interest] Bug in ConcurrentSkipListSet/ConcurrentSkipListMap?

Kasper Nielsen kasper at kav.dk
Sat Dec 4 07:04:30 EST 2010


That definitely looks like a bug.
I was able to easily reproduce it using latest from gee.cs.oswego.edu. 
on a 64 bit machine.

I used a bit simpler testcase.

final ConcurrentSkipListMap<Integer, Boolean> map = new 
ConcurrentSkipListMap<Integer, Boolean>();
final AtomicInteger al = new AtomicInteger();
ExecutorService es = Executors.newFixedThreadPool(8);
for (int i = 0; i < 8; i++) {
   es.submit(new Runnable() {
     public void run() {
       for (int i = 0; i < 1000000; i++) {
         Integer key = al.incrementAndGet();
         map.put(key, Boolean.TRUE);
         if (!map.containsKey(key)) {
           System.err.println("ohoh " + key);
         }
         map.remove(key);//works fine if you comment out remove
       }
     }
   });
}
es.shutdown();

Also i noticed its only when we combined inserts with removes that the 
problems occur.


Cheers
   Kasper


On 03-12-2010 17:58, Thorsten Möller wrote:
> 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());
> }
> }
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list