JDK-8062841 : ConcurrentHashMap.computeIfAbsent stuck in an endless loop
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Affected Version: 8,8u25,9
  • Priority: P4
  • Status: Closed
  • Resolution: Duplicate
  • Submitted: 2014-10-27
  • Updated: 2022-12-08
  • Resolved: 2015-09-21
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 9
9 b88Resolved
Related Reports
Duplicate :  
JDK-8134853 - Bulk integration of java.util.concurrent and related java.util classes
Duplicate :  
JDK-8190949 - Infinite loop of ConcurrentHashMap in recursive scene
Duplicate :  
JDK-8074374 - Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or ?fea
Description
FULL PRODUCT VERSION :
java version "1.8.0_25"
Java(TM) SE Runtime Environment (build 1.8.0_25-b17)
Java HotSpot(TM) 64-Bit Server VM (build 25.25-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Linux 3.13.0-37-generic #64-Ubuntu SMP Mon Sep 22 21:28:38 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux  

A DESCRIPTION OF THE PROBLEM :
ConcurrentHashMap is stuck in an endless loop in computeIfAbsent - the for-loop starting at line 1649.

tab=[
null,
null,
null,
null,
null,
null,
null,
null,
null=null,
null,
null,
null,
null,
class com.<redacted>.ClipboardPrepareImportService=com.<redacted>.ClipboardPrepareImportService@2ae00cd3,
null,
interface com.<redacted>.BackendConnectionGateway=Mock for BackendConnectionGateway, hashCode: 1117386246]

h=833174808

* the first if (line 1651) is skipped because tab is neither null nor empty
* the second if as well because f = tabAt(....) is equal to null=null (CHM$ReservationNode)
* the third if (line 1670) as well because fh = -3 (RESERVED)
* we fall back into the else block at line 1672

* tabAt(tab, i) == f is true (i=8) at line 1675
* the if at line 1676 is not satisfied because fh = -3
* the if at line 1696 is also not satisfied because f is an CHM$ReservationNode

* binCount = 0 so the if at line 1710 is also not satisfied.

Aaaand back to the beginning of the loop at 1649.


The searched value is not yet present when computeIfPresent is called -> the mapper function should be called but that never happens.

This only happens occasionally.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The mapping function is called and the computed value is added to the map and returned.
ACTUAL -
Endless loop.

REPRODUCIBILITY :
This bug can be reproduced occasionally.
Comments
Some discussion about recursive calls within computeIfAbsent is here: http://concurrency.markmail.org/thread/dixewqcvbbs5gzi2 (concurrency-interest mailing list, 2014-12-20, "ConcurrentHashMap computeIfAbsent")
08-12-2022
URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/6dd59c01f011 User: lana Date: 2015-10-21 22:17:00 +0000
21-10-2015
URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/6dd59c01f011 User: martin Date: 2015-10-14 01:19:13 +0000
14-10-2015
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?r1=1.258&r2=1.259&sortby=date
20-03-2015
Ignore my previous comment. We discovered some feasible diagnostic improvements that cover more user errors involving recursive map updates by functions supplied in computeIfAbsent, including the case attached in this report. Pending any further discussion on concurrency-interest, we should integrate to JDK9, then 8u.
22-12-2014
Response from the submitter: "I've been investigating the bug further in the mean time and I have a minimal example (see attachment). The problem is that we're doing a computeIfAbsent within another computeIfAbsent with an object that has accidentally the same hashCode (in the attached example "AaAa" and "BBBB" also have same hashCode). The documentation states that this is forbidden (mistake on our side) but it also states that this should throw "IllegalStateException - if the computation detectably attempts a recursive update to this map that would otherwise never complete". This is not the case. I would suggest that either a) the documentation is adjusted to make it more clear that the IllegalStateException is thrown on best effort basis. or b) the implementation is adjusted so that the IllegalStateException is really thrown."
03-12-2014
This suggestion is reasonable, but probably not one we can act on now. We would like to improve deadlock detection to help users debug their programs, and probably will. But currently, the underlying mechanisms to do this are too inefficient to routinely rely on in the case encountered here. For now though, we could at least make it clearer that detection is not guaranteed.
03-12-2014
I do not see a way to diagnose if there is a CHM problem here. The reservation mentioned may exist if some other thread is stuck while computing value, but there is no way to determine this from description.
04-11-2014
This bug doesn't include a repro recipe.
04-11-2014