Bug 53498 - Atomicity violation bugs because of misusing concurrent collections
Atomicity violation bugs because of misusing concurrent collections
Status: RESOLVED FIXED
Product: Tomcat 7
Classification: Unclassified
Component: Catalina
7.0.28
PC Mac OS X 10.4
: P2 normal (vote)
: ---
Assigned To: Tomcat Developers Mailing List
:
Depends on:
Blocks:
  Show dependency tree
 
Reported: 2012-07-02 21:19 UTC by Yu Lin
Modified: 2012-08-03 18:02 UTC (History)
0 users



Attachments
The patch that may fix the atomicity violation bugs. (2.98 KB, patch)
2012-07-02 21:19 UTC, Yu Lin
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yu Lin 2012-07-02 21:19:45 UTC
Created attachment 29021 [details]
The patch that may fix the atomicity violation bugs.

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
misusages. I found some misusages of ConcurrentHashMap in Tomcat
7.0.28, which may result in potential atomicity violation bugs or harm
the performance.

The code below is a snapshot of the code in file
java/org/apache/catalina/core/ApplicationContext.java from line 761 to
767 and line 1262 to 1266

L761        found = attributes.containsKey(name);
L762        if (found) {
L763            value = attributes.get(name);
L764            attributes.remove(name);
L765        } else {
L766            return;
L767        }
            ...
L1262       if (parameters.containsKey(name)) {
L1263           return false;
L1264       }
L1265
L1266       parameters.put(name, value);

In the code above, an atomicity violation may occur between lines 762
and 763. Suppose thread T1 executes line 761 and finds that the
concurrent hashmap "attributes" contains the key "name". Before thread
T1 executes line 763, another thread T2 removes the "name" key from
"attributes". Now thread T1 resumes execution at line 763 and will get
a null value for "name". Then the next line will throw a
NullPointerException when invoking the method on "name".

Second, the snapshot above has another atomicity violation. Let's look
at lines 1262 and 1266. Suppose a thread T1 executes line 1262 and
finds out the concurrent hashmap dose not contain the key
"name". Before it gets to execute line 1266, another thread T2 puts a
pair <name, v> in the concurrent hashmap "parameters". 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.

I found some similar misusages in other files:

In java/org/apache/catalina/ha/context/ReplicatedContext.java, similar
atomicity violation may occur when another thread T2 remove the key
"name" from concurrent hashmap "tomcatAttributes" before thread T1
executes line 172.

In java/org/apache/catalina/startup/HostConfig.java, suppose thread T1
executes line 1480 and finds out the concurrent hashmap dose not
contain the key "contextName". Before it executes line 1509, another
thread T2 puts a pair <contextName, v> in the concurrent hashmap
"deployed". Now thread T1 resumes execution and it will overwrite the
value written by thread T2. Indeed, the putIfAbsent method shoule be
used rather than put method at line 1509.
Comment 1 Mark Thomas 2012-07-02 21:22:31 UTC
Comment on attachment 29021 [details]
The patch that may fix the atomicity violation bugs.

Fix mime type so patch can be viewed in browser
Comment 2 Mark Thomas 2012-07-04 21:10:54 UTC
Many thanks for the analysis and patch.

The first three issues look valid on initial inspection although I suspect a closer analysis will show that not all of them are valid due to broader constraints that mean the code is, in reality, single threaded. Regardless, these three are fixed in trunk and 7.0.x and will be included in 7.0.30 onwards. I used the provided patch as a starting point although I did make some changes to make the code a little cleaner.

The fourth issue is definitely not valid since a Host will never permit multiple children with the same name. This change was not included in the fix.
Comment 3 Yu Lin 2012-07-06 22:58:48 UTC
Hello,

(In reply to comment #2)
> Many thanks for the analysis and patch.
>=
You are welcome. 

 
> Regardless,
> these three are fixed in trunk and 7.0.x and will be included in 7.0.30
> onwards. I used the provided patch as a starting point although I did make
> some changes to make the code a little cleaner.
> 
Great.

> The fourth issue is definitely not valid since a Host will never permit
> multiple children with the same name. This change was not included in the
> fix.

I'm not an expert on the domain of Host. Is there some code that creates unique keys "contextName" every single time when a thread executes "manageApp" method? If not, there could be still an atomicity violation: suppose thread T1 finds that map "deployed" doesn't contain key "contextName", so it moves to calculate the value "deployedApp". Before T1 puts "deployedApp" into the map, another thread T2 checks if "deployed" map doesn't contain key "contextName" and so it moves to create the value "deployedApp" and put it into the map. Now thread T1 resumes execution and overwrites what T2 previously put.
Comment 4 mikebell90 2012-08-03 18:02:06 UTC
probably a nit pick but the declarations really should be for ConcurrentMap not ConcurrentHashMap. There are variants of Concurrenthashmap coming in java8, and it's more correct to declare according to the interface