JDK-8205399 : Set node color on pinned HashMap.TreeNode deletion
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 8u192,10,11
  • Priority: P4
  • Status: Closed
  • Resolution: Fixed
  • Submitted: 2018-06-20
  • Updated: 2023-08-17
  • Resolved: 2018-08-10
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 11 JDK 12 JDK 8 Other
11.0.8-oracleFixed 12 b07Fixed 8u401Fixed openjdk8u392Fixed
Related Reports
Duplicate :  
JDK-8208633 - [TEST_BUG]: sanity/client/SwingSet/src/EditorPaneDemoTest: Failed with AssertionError from java.util.HashMap$TreeNode.moveRootToFront
Relates :  
JDK-8186171 - HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries
Description
vmTestbase/vm/gc/containers/Combination05/TestDescription.java failed in tier4 with the following failure(s):

...
Starting Thread[vm.gc.containers.ContainersTest$Mutator@3081d9dd,5,MainThreadGroup]
Starting Thread[vm.gc.containers.ContainersTest$Mutator@1d2c9a4,5,MainThreadGroup]
Starting Thread[vm.gc.containers.ContainersTest$Mutator@33aeb600,5,MainThreadGroup]
Starting Thread[vm.gc.containers.ContainersTest$Mutator@ccedf35,5,MainThreadGroup]
Starting Thread[vm.gc.containers.ContainersTest$Mutator@323fb040,5,MainThreadGroup]
Starting Thread[vm.gc.containers.ContainersTest$Mutator@25b7c04a,5,MainThreadGroup]
Exception in 
vm.gc.containers.ContainersTest$Mutator@64afc808
java.lang.AssertionError
	at java.base/java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1896)
	at java.base/java.util.HashMap$TreeNode.putTreeVal(HashMap.java:2061)
	at java.base/java.util.HashMap.putVal(HashMap.java:633)
	at java.base/java.util.HashMap.put(HashMap.java:607)
	at java.base/java.util.HashSet.add(HashSet.java:220)
	at vm.gc.containers.CollectionContainer.update(CollectionContainer.java:74)
	at vm.gc.containers.ContainersTest$Mutator.run(ContainersTest.java:82)
	at nsk.share.runner.ThreadsRunner$ManagedThread.run(ThreadsRunner.java:83)
Failures summary:
java.lang.AssertionError
	at java.base/java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1896)
	at java.base/java.util.HashMap$TreeNode.putTreeVal(HashMap.java:2061)
	at java.base/java.util.HashMap.putVal(HashMap.java:633)
	at java.base/java.util.HashMap.put(HashMap.java:607)
	at java.base/java.util.HashSet.add(HashSet.java:220)
	at vm.gc.containers.CollectionContainer.update(CollectionContainer.java:74)
	at vm.gc.containers.ContainersTest$Mutator.run(ContainersTest.java:82)
	at nsk.share.runner.ThreadsRunner$ManagedThread.run(ThreadsRunner.java:83)
----------System.err:(40/2060)----------
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
Creating container: size = 100 count = 330972
nsk.share.TestFailure: Test exit code: 97
	at nsk.share.test.Tests$TestRunner.execute(Tests.java:90)
	at nsk.share.test.Tests$TestRunner.run(Tests.java:96)
	at nsk.share.gc.GC.runTest(GC.java:114)
	at vm.gc.containers.ContainersTest.main(ContainersTest.java:157)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:566)
	at com.sun.javatest.regtest.agent.MainWrapper$MainThread.run(MainWrapper.java:115)
	at java.base/java.lang.Thread.run(Thread.java:832)

JavaTest Message: Test threw exception: nsk.share.TestFailure: Test exit code: 97
JavaTest Message: shutting down test
Comments
Fix Request (8u) Fixes the invariant bug in HashMap. Reproduces as assertion failure with the new regression test. The correctness impact looks low, since we are doing the intrinsically safe red -> black repainting for the (sub-)root. tier1 tests pass.
31-05-2023
A pull request was submitted for review. URL: https://git.openjdk.org/jdk8u-dev/pull/325 Date: 2023-05-30 08:42:32 +0000
30-05-2023
Just tried the TreeBinAssert.java attached to the issue with the recent JDK 8 build (Corretto 8u372), and it fails: $ /Library/Java/JavaVirtualMachines/amazon-corretto-8.jdk/Contents/Home/bin/java -ea -esa TreeBinAssert java.util.HashMap fails with java.lang.AssertionError at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1873) at java.util.HashMap$TreeNode.putTreeVal(HashMap.java:2038) at java.util.HashMap.putVal(HashMap.java:639) at java.util.HashMap.put(HashMap.java:613) at TreeBinAssert.testMap(TreeBinAssert.java:93) at TreeBinAssert.main(TreeBinAssert.java:70) Looks like JDK-8186171 is in 8u as well, and so it exposes the same failure. I would mark the affected versions to reflect that.
30-05-2023
Fix request (11u) I would like to downport this for parity with 11.0.8-oracle. Applies clean.
05-03-2020
URL: http://hg.openjdk.java.net/jdk/jdk/rev/f23aeb97ae17 User: bchristi Date: 2018-08-10 19:07:05 +0000
10-08-2018
Thank you very much, Doug! The bug started reproducing in JDK 10 after this change to removeTreeNode() was put in via JDK-8186171 : @@ -2089,8 +2092,11 @@ return; if (root.parent != null) root = root.root(); - if (root == null || root.right == null || - (rl = root.left) == null || rl.left == null) { + if (root == null + || (movable + && (root.right == null + || (rl = root.left) == null + || rl.left == null))) { tab[index] = first.untreeify(map); // too small return; }
03-08-2018
Thanks Brent. for isolating this! The problem was failure to set root color in pinned node deletion case, which is harmless but wrong with respect to invariant checks, and should be fixed. I wonder why it did not show up until jdk10? diff -r 01e20d8850e3 src/java.base/share/classes/java/util/HashMap.java --- a/src/java.base/share/classes/java/util/HashMap.java Thu May 31 18:47:21 2018 -0400 +++ b/src/java.base/share/classes/java/util/HashMap.java Thu Aug 02 19:22:38 2018 -0400 @@ -2148,7 +2148,7 @@ if (replacement != p) { TreeNode<K,V> pp = replacement.parent = p.parent; if (pp == null) - root = replacement; + (root = replacement).red = false; else if (p == pp.left) pp.left = replacement; else
02-08-2018
I got Mach5 to reproduce the failure a few times with an instrumented build. I've written a standalone LinkedHashSet test to reproduce the assertion failure - attached. The assertion started happening in JDK 10.
02-08-2018
Simplified the test down to a single file.
02-08-2018
My tests starts failing in JDK 10 b26. The problem happens with Iterator.remove() (and not the collection's remove() method). Maybe JDK-8186171?
01-08-2018
It appears to be reproducible for about 1 in 5 runs with just the following arguments: -ea -esa -Xcomp Still i don't think it's necessarily a -Xcomp related issue given a similar failure has been observed in a Swing test executed with just "-ea -esa".
28-06-2018
I can now reproduce regularly through mach5, which gives a basis to add more diagnostics. At the moment it is really very unclear what the cause is (GC, HashMap code, or HashMap assertion code, etc) and it could take a while to determine that. Since the test failure only occurs when system assertions are enabled i would argue there is a clear workaround. Further it also affects only tier4 tests (IIUC) and no other non-system-assertion related failures have been reported for HashSet. Thus I don't think the high priority nor a specific target accurately reflects the current situation.
27-06-2018
ILW: M (not a dev blocker), L (occurs rarely), M (can problem-list the test if necessary) => P4
27-06-2018
I just tried with latest jdk/jdk10 and the assertion also fails the same way if run repeatedly (6 times out of 211 right now). This is the only test that fails with this assert, but we do not very frequently run all tests with -ea -esa (and certainly not hundreds of times). (Note that in jdk10 the test is closed source; you need to manually get the test from the jdk11 repo if you want to try).
27-06-2018
Is there any more prior history of this test intermittently failing? It would be useful to see if it fails on builds prior to the first build observed to fail. I cannot reproduced locally. I eyeballed the test as AFAICT there should be no multi-threaded access to non-thread-safe collections.
27-06-2018
The assert in question was introduced by: changeset: 19806:dda89341ee2d user: psandoz date: 2013-09-04 09:34 +0200 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black) 8012913: LinkedHashMap key/value/entry spliterators should report ORDERED Reviewed-by: mduigou, forax, bchristi, alanb Contributed-by: Doug Lea <dl@cs.oswego.edu>, Paul Sandoz <paul.sandoz@oracle.com> (I was a little surprised by the presence of assert here - generally we keep it out of performance critical classes) It seems unlikely that there is an actual bug in HashMap. A bug in the test leading to multi-threaded access seems more likely. For further debugging, the assertions in checkInvariants can be expanded to be more granular and produce informative exceptions.
26-06-2018
This reproduces like around 1 in 20 times with -ea -esa enabled. Since this does not seem to affect further execution at all (no crashes, no obvious other issues without -ea -esa) potentially the assert is wrong. There do not seem to be any obvious test bugs either (i.e. like using the collection in multiple threads). There is also a similar issue open for some time now, asking class library devs to analyze.
26-06-2018