Bug ID: JDK-7004737 ConcurrentSkipListMap.contains can return outdated values when contending with concurrent removes

Versions (Unresolved/Resolved/Fixed)

The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.

JDK 7
7Resolved

http://cs.oswego.edu/pipermail/concurrency-interest/2010-December/007539.html

Thorsten M��ller reports:

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.

EVALUATION The fix for this bug was integrated as part of CR 7005424: Resync java.util.concurrent classes with Dougs CVS - Jan 2011. see: http://hg.openjdk.java.net/jdk7/tl/jdk/diff/cb3ecb5e4ce5/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java

19-01-2011

WORK AROUND You can get the updated class now (either standalone or as part of jsr166.jar) and run using -Xbootclass:/p switches -- see http://gee.cs.oswego.edu/dl/concurrency-interest/index.html

05-12-2010

EVALUATION Doug Lea writes: Thanks for reporting this! Sorry about the problem. In case you are curious, this was due to the lack of a staleness check in a bypass for contains. Which as it turns out was not worthwhile in repaired form, so the bypass is now removed. This will probably take a while to propagate to releases, but in the mean time you can get the updated class now (either standalone or as part of jsr166.jar) and run using -Xbootclass:/p switches -- see http://gee.cs.oswego.edu/dl/concurrency-interest/index.html

05-12-2010