Possible atomicity violations when composing concurrent collections operations

[Yu Lin]

Hi,

My name is Yu Lin. I'm a Ph.D. student in the CS department at
UIUC. I'm currently doing research on mining Java concurrent library
misuses. I found some uses of concurrent collections in OpenJDK8 may
result in potential atomicity violation bugs. I just posted this issue
to the mailing list of OpenJdk7u but I was suggested to post here because
OpenJDK8 is more active recently.

The code below is a snapshot of the code in file
jdk/src/share/classes/java/security/Security.java
from line 669 to 681

L669   private static Class getSpiClass(String type) {
L670        Class clazz = spiMap.get(type);
L671        if (clazz != null) {
L672            return clazz;
L673        }
L674        try {
L675            clazz = Class.forName("java.security." + type + "Spi");
L676            spiMap.put(type, clazz);
L677            return clazz;
L678        }
            ...
L681   }

In the code above, there might be an atomicity violation: suppose a
thread T1 executes line 670 and finds out the concurrent hashmap
"spiMap" does not contain the key "type". Before it gets to execute
line 676, another thread T2 puts a pair <type, v> in the map
"spiMap". Now thread T1 resumes execution and it will overwrite the
value written by thread T2. Thus, the code no longer preserves the
"put-if-absent" semantics, and thread T2 will return a "clazz" object
that is not in the map at line 677. If such interleaving may happen,
it may result in buggy behavior. I assume that it may happen because
the concurrent hashmap is usually used in a multithreaded
context. This violation can be avoided by using "putIfAbsent" method.

There are many other places in Helix that have the same code patterns
as the above two examples, but I'm not sure which will lead to bug and
which not. If you think this kind of problem is important and may lead
to buggy behavior, I can list all of them.

Moreover, there are other two kinds of potential bugs:
in jdk/src/share/classes/java/lang/Thread.java from line 16662 to 1668,

L1662   Boolean result = Caches.subclassAudits.get(key);
L1663   if (result == null) {
L1664       result = Boolean.valueOf(auditSubclass(cl));
L1665       Caches.subclassAudits.putIfAbsent(key, result);
L1666   }

L1668   return result.booleanValue();

If thread T2 puts a pair <key, result2> after thread T1 finds "key"
isn't in the map but just before T1 executes line 1665, the <key,
result> in T1 won't be put. So T1 returns a "result" which is not in
the map. Actually, the return value of "putIfAbsent" method should be
checked here.

I append a patch to show the fix of the above problems. I can also list
all of such code I found if you need.

Regards,
Yu

==================================================

diff -r 79c9847d4a5f src/share/classes/java/lang/Thread.java
--- a/src/share/classes/java/lang/Thread.java   Thu Aug 02 15:36:39 2012 -0700
+++ b/src/share/classes/java/lang/Thread.java   Fri Aug 03 11:14:13 2012 -0500
@@ -1662,7 +1662,9 @@
         Boolean result = Caches.subclassAudits.get(key);
         if (result == null) {
             result = Boolean.valueOf(auditSubclass(cl));
-            Caches.subclassAudits.putIfAbsent(key, result);
+            Boolean tmpResult = Caches.subclassAudits.putIfAbsent(key, result);
+            if(tmpResult != null)
+                result = tmpResult;
         }

         return result.booleanValue();
diff -r 79c9847d4a5f src/share/classes/java/security/Security.java
--- a/src/share/classes/java/security/Security.java     Thu Aug 02
15:36:39 2012 -0700
+++ b/src/share/classes/java/security/Security.java     Fri Aug 03
11:14:13 2012 -0500
@@ -658,7 +658,7 @@
     }

     // Map containing cached Spi Class objects of the specified type
-    private static final Map<String, Class<?>> spiMap =
+    private static final ConcurrentHashMap<String, Class<?>> spiMap =
             new ConcurrentHashMap<>();

     /**
@@ -673,7 +673,9 @@
         }
         try {
             clazz = Class.forName("java.security." + type + "Spi");
-            spiMap.put(type, clazz);
+            Class<?> tmpClazz = spiMap.putIfAbsent(type, clazz);
+            if(tmpClazz != null)
+                clazz = tmpClazz;
             return clazz;
         } catch (ClassNotFoundException e) {
             throw new AssertionError("Spi class not found", e);