Possible atomicity violations when composing concurrent collections operations (original) (raw)

Yu Lin yu.lin.86 at gmail.com
Thu Aug 2 11:52:22 PDT 2012

• Previous message: Should back-ports cc the mailing lists for the area? (was Re: [7u8] Request for approval: 7113017: Use POSIX compliant include file headers in sun/awt/medialib/mlib_types.h)
• Next message: Possible atomicity violations when composing concurrent collections operations
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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 OpenJDK7u may result in potential atomicity violation bugs or harm the performance.

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

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

In the code above, there might be an atomicity violation: suppose a thread T1 executes line 671 and finds out the concurrent hashmap "spiMap" does not contain the key "type". Before it gets to execute line 677, 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 678. 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.

Also, there are some code in OpenJDK7u that avoid the above interleaving by adding synchronizations. For example in jdk/src/share/classes/java/lang/ClassLoader.java from line 932 to 937

L932 synchronized (this) { L933 pcerts = package2certs.get(pname); L934 if (pcerts == null) { L935 package2certs.put(pname, (certs == null? nocerts:certs)); L936 } L937 }

However, if we use "putIfAbsent" at line 592, the synchronization at line 588 is no longer needed. Generally, using "putIfAbsent" has better performace than synchronizing a concurrent hashmap.

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 1659 to 1665,

L1659 Boolean result = Caches.subclassAudits.get(key); L1660 if (result == null) { L1661 result = Boolean.valueOf(auditSubclass(cl)); L1662 Caches.subclassAudits.putIfAbsent(key, result); L1663 }

L1665 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 1662, 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.

Another possible atomicity vioaltion may happen at line 892 in jdk/src/share/classes/sun/font/FileFontStrike.java:

L891 if (boundsMap == null) { L892 boundsMap = new ConcurrentHashMap<Integer, Rectangle2D.Float>(); L893 } // some <key, value> pairs are put into "boundsMap"

A possible buggy scenario is both threads T1 and T2 finds "boundsMap" is null at the same time (line 891). After T1 creates a new empty map and puts some <key, value> pairs into "boundsMap", T2 also creates an empty map and writes to "boundsMap". Then the <key, value> pairs put by T1 will be lost. If this scenario may happen and lead to bug, we have to add synchronization when initializing "boundsMap".

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

Regards, Yu

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

diff -r 7daf4a4dee76 src/share/classes/java/lang/ClassLoader.java --- a/src/share/classes/java/lang/ClassLoader.java Mon May 07 14:59:29 2012 -0700 +++ b/src/share/classes/java/lang/ClassLoader.java Thu Aug 02 11:50:46 2012 -0500 @@ -929,11 +929,10 @@ } Certificate[] pcerts = null; if (parallelLockMap == null) {

•        synchronized (this) {

•            pcerts = package2certs.get(pname);

•            if (pcerts == null) {

•                package2certs.put(pname, (certs == null? nocerts:certs));

•            }

•        pcerts = package2certs.get(pname);

•        if (pcerts == null) {

•            ((ConcurrentHashMap<String, Certificate[]>)package2certs)

•                .putIfAbsent(pname, (certs == null? nocerts:certs));
         }
     } else {
         pcerts = ((ConcurrentHashMap<String, Certificate[]>)package2certs).

diff -r 7daf4a4dee76 src/share/classes/java/lang/Thread.java --- a/src/share/classes/java/lang/Thread.java Mon May 07 14:59:29 2012 -0700 +++ b/src/share/classes/java/lang/Thread.java Thu Aug 02 11:50:46 2012 -0500 @@ -1659,7 +1659,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 7daf4a4dee76 src/share/classes/java/security/Security.java --- a/src/share/classes/java/security/Security.java Mon May 07 14:59:29 2012 -0700 +++ b/src/share/classes/java/security/Security.java Thu Aug 02 11:50:46 2012 -0500 @@ -660,7 +660,7 @@ }

 // Map containing cached Spi Class objects of the specified type

• private static final Map<String, Class> spiMap = new ConcurrentHashMap<>();

• private static final ConcurrentHashMap<String, Class> spiMap =

new ConcurrentHashMap<>();

 /**
  * Return the Class object for the given engine type

@@ -674,7 +674,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); diff -r 7daf4a4dee76 src/share/classes/sun/font/FileFontStrike.java --- a/src/share/classes/sun/font/FileFontStrike.java Mon May 07 14:59:29 2012 -0700 +++ b/src/share/classes/sun/font/FileFontStrike.java Thu Aug 02 11:50:46 2012 -0500 @@ -887,9 +887,10 @@ * up in Java code either. */ Rectangle2D.Float getGlyphOutlineBounds(int glyphCode) {

•    if (boundsMap == null) {

•        boundsMap = new ConcurrentHashMap<Integer, Rectangle2D.Float>();

•    synchronized (boundsMap) {

•        if (boundsMap == null) {

•            boundsMap = new ConcurrentHashMap<Integer,

Rectangle2D.Float>();

•        }
     }
  
     Integer key = Integer.valueOf(glyphCode);

• Previous message: Should back-ports cc the mailing lists for the area? (was Re: [7u8] Request for approval: 7113017: Use POSIX compliant include file headers in sun/awt/medialib/mlib_types.h)
• Next message: Possible atomicity violations when composing concurrent collections operations
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the jdk7u-dev mailing list