Possible atomicity violations when composing concurrent collections operations
Yu Lin
yu.lin.86 at gmail.com
Mon Aug 6 09:56:33 PDT 2012
Hi,
I agree with Vitaly that benign races is a valid technique, though it's hard
to say whether it's good or not from the perspective of maintenance.
I think I can list all the locations that have the same kind of races
so that we
can check again whether that are benign or not.
Actually, they are all in the check-then-act format like:
Value v = map.get(key);
if(v == null) { // or "if(v != null)"
v = createValue();
map.put(key, v);
}
... // "v" is used here
To eliminate such atomicity violations while still preserve the
semantics of the
original code, we can replace "put" method with "putIfAbsent" (if the
condition is "v == null")
or "replace" method (if the condition is "v != null"). However, I
agree that "putIfAbsent" or
"replace" has somewhat worse performance than "put".
Here are the locations I found, note that I've already filtered out
two places where I
can make sure the races are benign:
jdk/src/share/classes/java/security/Signature.java line 298
jdk/src/share/classes/java/text/SimpleDateFormat.java line 668
jdk/src/share/classes/sun/font/SunFontManager.java lines 761, 849, 1180
jdk/src/share/classes/sun/font/FileFontStrike.java line 900
jdk/src/share/classes/sun/font/Font2D.java line 361
jdk/src/share/classes/sun/font/FontUtilities.java line 429
jdk/src/share/classes/sun/security/pkcs11/TemplateManager.java line 107
jdk/src/share/classes/sun/util/LocaleServiceProviderPool.java lines 453, 460
Thanks,
Yu
2012/8/6 Vitaly Davidovich <vitalyd at gmail.com>:
> 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