Possible atomicity violations when composing concurrent collections operations

Ludwig, Mark ludwig.mark at siemens.com
Mon Aug 6 12:56:11 PDT 2012


Hi Vitaly,

I misunderstood something, because now that I've looked at several of these, I agree the code is okay.  (I certainly agree that it's a desirable technique to allow races to proceed asynchronously whenever possible and valid.)

Cheers,
Mark

From: Vitaly Davidovich [mailto:vitalyd at gmail.com] 
Sent: Monday, August 06, 2012 10:35 AM
To: Ludwig, Mark
Cc: Yu Lin; jdk8-dev at openjdk.java.net
Subject: RE: Possible atomicity violations when composing concurrent collections operations

Hi Mark,
Exploiting benign data races in the name of performance is a valid technique - another prominent example is String.hashcode().  I agree that they're more subtle and require meticulous coding/maintenance to make sure the properties that allow for this remain true (e.g. idempotence).  It's unclear to me whether the two JDK examples discussed here were coded that way for performance reasons, but they don't appear to be bugs in the strict definition of a bug - they work properly in the form they're in today.  Class.forName() is unlikely to ever change where the returned value is not identical across invocations, likewise for Boolean.booleanValue.  So I think these two examples are not brittle.
It goes without saying that even changing straightforward code can introduce bugs - that's just the nature of change.  Writing benign data races is tricky and requires understanding of the platform, but it's a valid approach.  Can you elaborate on what specifically you think is a problem in these two examples, and under what "trivial"/easily-overlooked change these methods would break?
Thanks
Sent from my phone
On Aug 6, 2012 9:56 AM, "Ludwig, Mark" <ludwig.mark at siemens.com> wrote:
The problems look real to me.

Vitaly, doesn't your analysis that these problems are benign assume that the consumers and circumstances around these APIs never change?  Put another way, these errors might be benign now, but that does not mean they will remain benign forever, does it?  With your response, it appears that you mean to discount the criticality of the errors, but intentions are difficult to discern through e-mail.

Cheers,
Mark

> -----Original Message-----
> From: jdk8-dev-bounces at openjdk.java.net [mailto:jdk8-dev-
> bounces at openjdk.java.net] On Behalf Of Vitaly Davidovich
> Sent: Friday, August 03, 2012 5:30 PM
> To: Yu Lin
> Cc: jdk8-dev at openjdk.java.net
> Subject: Re: Possible atomicity violations when composing concurrent
> collections operations
>
> In both of the examples you mentioned, the race seems benign.  In the first
> example, a Class may be returned that's not in the map anymore if it's
> overwritten, but Class.forName() with exact same args should return the
> same instance of Class.  Likewise in the second example the return value is
> a primitive boolean, so even if two threads race, it shouldn't matter.
>
> The race would be an issue if identity equality is required and the
> creation/construction of the object inside the method does not itself
> guarantee identity, but I don't see either of these issues in these 2
> examples.
>
> Cheers,
> Vitaly
>
> Sent from my phone
> On Aug 3, 2012 6:06 PM, "Yu Lin" <yu.lin.86 at gmail.com> wrote:
>
> > 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);
> >


More information about the jdk8-dev mailing list