I think there is a data race in the class java.util.concurrent.ConcurrentHashMap.
When reading from the fields TreeNode.left and TreeNode.right using get and writing to those fields using put those fields are not synchronized. I think they both should be volatile similar to the field next of the class Node. I have created a test in the git project https://github.com/vmlens/race-conditions-java.git to reproduce the data race using https://vmlens.com, a tool I have written to test multi-threaded Java. Regards Thomas Krieger _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
> I think there is a data race in the class java.util.concurrent.ConcurrentHashMap.
> When reading from the fields TreeNode.left and TreeNode.right using get and writing to those fields using put those fields are not synchronized. > I think they both should be volatile similar to the field next of the class Node. All the fields in TreeNode are only read/written while synchronizing on the TreeBin they belong to. See, for example, http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?revision=1.323&view=markup#l1902 Normal /Kasper _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
Write only is o.k. Reading and writing using the class Node is also o.k. Only reading and writing using the class TreeNode leads to a data race.
Here is a scenario which leads to the data race: The ConcurrentHashMap is filled with 10 keys with the same hash code, more than the TREEIFY_THRESHOLD of 8. So the class TreeNode is used. The first Thread calls put, the second Thread calls get. The first Thread is executing the following operations in the given method. I only show synchronization actions and the read and write of the data race: ConcurrentHashMap.putVal(java.lang.Object,java.lang.Object,boolean) read ConcurrentHashMap.table ConcurrentHashMap.tabAt(ConcurrentHashMap$Node[],int) read Unsafe or VarHandle array access ConcurrentHashMap.put(java.lang.Object,java.lang.Object) monitor enter ConcurrentHashMap.tabAt(ConcurrentHashMap$Node[],int) read Unsafe or VarHandle array access ConcurrentHashMap$TreeBin.putTreeVal(int,java.lang.Object,java.lang.Object) read ConcurrentHashMap$TreeBin.first ConcurrentHashMap$TreeBin.putTreeVal(int,java.lang.Object,java.lang.Object) write ConcurrentHashMap$TreeBin.first ConcurrentHashMap$TreeBin.putTreeVal(int,java.lang.Object,java.lang.Object) write <<race>> ConcurrentHashMap$TreeNode.left The write of the race happens here ConcurrentHashMap.put(java.lang.Object,java.lang.Object) monitor exit ConcurrentHashMap.addCount(long,int) read ConcurrentHashMap.counterCells ConcurrentHashMap.addCount(long,int) read ConcurrentHashMap.baseCount ConcurrentHashMap.addCount(long,int) compare and swap ConcurrentHashMap.baseCount ConcurrentHashMap.addCount(long,int) read ConcurrentHashMap.sizeCtl Now the second thread executes the following synchronization actions and read of the field left: ConcurrentHashMap.get(java.lang.Object) read ConcurrentHashMap.table ConcurrentHashMap.tabAt(ConcurrentHashMap$Node[],int) read Unsafe or VarHandle array access ConcurrentHashMap$TreeBin.find(int,java.lang.Object) read ConcurrentHashMap$TreeBin.first ConcurrentHashMap$TreeBin.find(int,java.lang.Object) read ConcurrentHashMap$TreeBin.lockState ConcurrentHashMap$TreeBin.find(int,java.lang.Object) compare and swap ConcurrentHashMap$TreeBin.lockState ConcurrentHashMap$TreeNode.findTreeNode(int,java.lang.Object,java.lang.Class) read <<race>> ConcurrentHashMap$TreeNode.left The read of the race happens here ConcurrentHashMap$TreeBin.find(int,java.lang.Object) compare and swap ConcurrentHashMap$TreeBin.lockState ConcurrentHashMap.get(java.lang.Object) read ConcurrentHashMap$Node.val Here is a similar scenario with the class Node node instead of TreeNode. The ConcurrentHashMap is filled with 3 keys with the same hash code, less than the TREEIFY_THRESHOLD of 8. So the class Node is used. It is almost the same as the scenario for the class TreeNode only that this time the field next which is used for traversing the link structure is volatile: The first Thread calls put, the second Thread calls get. The first Thread executes the following synchronization actions ConcurrentHashMap.putVal(java.lang.Object,java.lang.Object,boolean) read ConcurrentHashMap.table ConcurrentHashMap.tabAt(ConcurrentHashMap$Node[],int) read Unsafe or VarHandle array access ConcurrentHashMap.put(java.lang.Object,java.lang.Object) monitor enter ConcurrentHashMap.tabAt(ConcurrentHashMap$Node[],int) read Unsafe or VarHandle array access ConcurrentHashMap.putVal(java.lang.Object,java.lang.Object,boolean) 3 * read ConcurrentHashMap$Node.next ConcurrentHashMap.putVal(java.lang.Object,java.lang.Object,boolean) write ConcurrentHashMap$Node.next ConcurrentHashMap.put(java.lang.Object,java.lang.Object) monitor exit ConcurrentHashMap.addCount(long,int) read ConcurrentHashMap.counterCells ConcurrentHashMap.addCount(long,int) read ConcurrentHashMap.baseCount ConcurrentHashMap.addCount(long,int) compare and swap ConcurrentHashMap.baseCount ConcurrentHashMap.addCount(long,int) read ConcurrentHashMap.sizeCtl Now the second thread executes the following synchronization actions ConcurrentHashMap.get(java.lang.Object) read ConcurrentHashMap.table ConcurrentHashMap.tabAt(ConcurrentHashMap$Node[],int) read Unsafe or VarHandle array access ConcurrentHashMap.get(java.lang.Object) 3 * read ConcurrentHashMap$Node.next ConcurrentHashMap.get(java.lang.Object) read ConcurrentHashMap$Node.val Regards Thomas > On 26 March 2020 09:35 Kasper Nielsen <[hidden email]> wrote: > > > > I think there is a data race in the class java.util.concurrent.ConcurrentHashMap. > > When reading from the fields TreeNode.left and TreeNode.right using get and writing to those fields using put those fields are not synchronized. > > I think they both should be volatile similar to the field next of the class Node. > > All the fields in TreeNode are only read/written while synchronizing > on the TreeBin they belong to. > See, for example, > http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?revision=1.323&view=markup#l1902 > > Normal > > /Kasper Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest |
Free forum by Nabble | Edit this page |