Potential data race in java.util.concurrent.ConcurrentHashMap at the fields TreeNode.left and right

[JSR166 Concurrency mailing list]

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

[JSR166 Concurrency mailing list]

> 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

[JSR166 Concurrency mailing list]

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