To avoid data corruption in multithreaded Java programs, shared data must be protected from concurrent modifications and accesses. This Locking can be performed at the object level by using synchronized methods or , synchronized blocks, or by using the java.util.concurrent
dynamic lock objects. However, excessive use of locking may can result in deadlocks (See CON08-J. Do not call alien methods that synchronize on the same objects as any callers in the execution chain). unmigrated-wiki-markup
"The Java programming language neither prevents deadlocks nor requires detection of deadlock conditions." \[[JLS 05|AA. Java References#JLS 05]\]. Deadlocks can arise when two or more threads request and release locks in different orders. Consequently, to avoid deadlock, locks should be acquired and released in the same order and synchronization should be limited to where it is absolutely necessary. For instance, to avoid deadlocks in an applet, the {{paint()}}, {{dispose()}}, {{stop()}}, and {{destroy()}} methods should not be synchronized because they are always called and used from dedicated threads.their detection [JLS 2015]. Deadlock can occur when two or more threads request and release locks in different orders. Consequently, programs are required to avoid deadlock by acquiring and releasing locks in the same order.
Additionally, synchronization should be limited to cases where it is absolutely necessary. For example, the paint()
, dispose()
, stop()
, and destroy()
methods should never be synchronized in an applet because they are always called and used from dedicated threads. Furthermore, the Thread.stop()
and Thread.destroy()
methods are deprecated (see THI05-J. Do not use Thread.stop() to terminate threads for more information).
This rule also applies to programs that need to work with a limited set of resources. For example, liveness issues can arise when two Deadlocks can also arise when two or more threads are waiting for each other to release resources such as database connections. The advice of this guideline also applies to these casesThese issues can be resolved by letting each waiting thread retry the operation at random intervals until they successfully acquire the resource.
Noncompliant Code Example (Different Lock Orders)
This noncompliant code example can can deadlock because of excessive synchronization. Assume that an attacker has two bank accounts and is capable of requesting two depositAllAmount()
operations in succession, one each from the two threads started in main()
. The balanceAmount
field represents the total balance available for a particular BankAccount
object. Users are allowed to initiate an operation that atomically transfers a specified amount from one account to another.
Code Block | ||
---|---|---|
| ||
final | ||
Code Block | ||
| ||
class BankAccount { private intdouble balanceAmount; // Total amount in bank account private BankAccount(intdouble balance) { this.balanceAmount = balance; } // Deposits the amount from this object instance // to BankAccount instance argument ba private void depositAllAmountdepositAmount(BankAccount ba, double amount) { synchronized (this) { synchronized (ba) { ba.balanceAmount += this.balanceAmount; if (amount > balanceAmount) { this.balanceAmount =throw 0; // Withdraw all amount from this instance new IllegalArgumentException( ba.displayAllAmount(); // Display the new balanceAmount in ba (may cause deadlock) "Transfer cannot be completed" ); } } } ba.balanceAmount += amount; private synchronized void displayAllAmount() { this.balanceAmount System.out.println(balanceAmount)-= amount; } public static void } } public static void initiateTransfer(final BankAccount first, final BankAccount second, final double amount) { Thread ttransfer = new Thread(new Runnable() { public void run() { first.depositAllAmountdepositAmount(second, amount); } }); ttransfer.start(); } } |
Objects of class BankAccount
represent bank accounts. The balanceAmount
field represents the total balance amount available for a particular object (bank account). A user is allowed to initiate an operation deposit all amount that transfers the balance amount from one account to another. This is equivalent to closing a bank account and transferring the balance to a different (existing or new) account.
Objects of this class are deadlock-prone. An attacker may cause the program to construct two threads that initiate balance transfers from two different BankAccount
object instances, a
and b
. Consider the following code that does this:
this class are prone to deadlock. An attacker who has two bank accounts can construct two threads that initiate balance transfers from two different BankAccount
object instances a
and b
. For example, consider the following code:
Code Block |
---|
BankAccount a = new BankAccount(5000);
BankAccount b |
Code Block |
BankAccount a = new BankAccount(50006000); BankAccount b = new BankAccount(6000); .initiateTransfer(a, b, 1000); // starts thread 1 BankAccount.initiateTransfer(b, a, 1000); // starts thread 2 |
The two transfers are Each transfer is performed in their own threads, from instance a
to b
and b
to a
its own thread. The first thread atomically transfers the amount from a
to b
by depositing the balance from a
to it in account b
and then withdrawing the entire balance same amount from a
. The second thread performs the reverse operation, ; that is, it transfers the balance amount from b
to a
and withdraws the balance from b
. When executing depositAllAmountdepositAmount()
, the first thread acquires a lock on object a
. It is possible for the The second thread to could acquire a lock on object b
before the first thread can lock b
. Subsequently, the first thread would request a lock on b
, which is already held by the second thread. The second thread would request a lock on a
, which is already held by the first thread. This constitutes a deadlock condition , as because neither thread can proceed.
This noncompliant code example may or may not deadlock, depending on the scheduling details of the platform. Deadlock can occur occurs when (1) two threads request the same two locks in different orders, and (2) each thread obtains a lock that prevents the other thread from completeing completing its transfer. Deadlock might not occur is avoided when two threads request the same two locks , but one thread completes its transfer before the other thread begins. Deadlock also cannot occur Similarly, deadlock is avoided if the two threads request the same two locks in the same order (which would happen if they both transfer money from one account to a second account) , or if two simultaneous transfers occur involving distinct accounts occur concurrently.
Compliant Solution (
...
Private Static Final Lock Object)
The deadlock can be avoided by using This compliant solution avoids deadlock by synchronizing on a private static final internal lock object before performing any account transfers.:
Code Block | ||
---|---|---|
| ||
final class BankAccount { private intdouble balanceAmount; // Total amount in bank account private static final Object lock = new Object(); private BankAccount(intdouble balance) { this.balanceAmount = balance; } this.lock = new Object(); } // Deposits the amount// Deposits the amount from this object instance // to BankAccount instance argument ba private void depositAllAmountdepositAmount(BankAccount ba, double amount) { synchronized (lock) { ba.balanceAmount += this.balanceAmount;if (amount > balanceAmount) { this.balanceAmount = 0;throw // Withdraw all amount from this instance new IllegalArgumentException( ba.displayAllAmount(); // Display the new balanceAmount in ba (may cause deadlock) "Transfer cannot be completed"); } } private void displayAllAmount() { synchronized (lock) { ba.balanceAmount += amount; Systemthis.out.println(balanceAmount)balanceAmount -= amount; } } public static void initiateTransfer(final BankAccount first, final BankAccount second), { final double amount) { Thread ttransfer = new Thread(new Runnable() { @Override public void run() { first.depositAllAmountdepositAmount(second, amount); } }); ttransfer.start(); } } |
In this scenario, if deadlock cannot occur when two threads with two different BankAccount
objects try to transfer to each othersother's accounts simultaneously, deadlock cannot occur. One thread will acquire the private lock, complete its transfer, and release the lock , before the other thread can proceed.
This solution comes with imposes a performance penalty because a private static lock restricts the system to performing only one transfer at a timetransfers sequentially. Two transfers involving four distinct accounts (with distinct target accounts) may not happen cannot be performed concurrently. The impact of this This penalty increases considerably as the number of BankAccount
objects increase. Consequently, this solution does not fails to scale very well.
Compliant Solution (
...
Ordered Locks)
This compliant solution ensures that multiple locks are acquired and released in the same order. It requires that an a consistent ordering over BankAccount
objects is available. The ordering is enforced by having the class BankAccount
implement . Consequently, the BankAccount
class implements the java.lang.Comparable
interface and overriding overrides the compareTo()
method.
Code Block | ||
---|---|---|
| ||
final class BankAccount implements Comparable<BankAccount> { private intdouble balanceAmount; // Total amount in bank account private final Object lock; private final long id; // uniqueUnique for each BankAccount private static longfinal AtomicLong nextID = new AtomicLong(0); // nextNext unused idID private BankAccount(intdouble balance) { this.balanceAmount = balance; this.lock = new Object(); this.id = this.nextID++nextID.getAndIncrement(); } @Override public int compareTo(BankAccount ba) { ifreturn (this.id <> ba.id) { ? 1 : (this.id < ba.id) return? -1; } if (this.id > ba.id) { return 1; } return : 0; } // Deposits the amount from this object instance // to BankAccount instance argument ba privatepublic void depositAllAmountdepositAmount(BankAccount ba, double amount) { BankAccount former, latter; if (compareTo(ba) < 0) { former = this; latter = ba; } else { former = ba; latter = this; } synchronized (former) { synchronized (latter) { ba.balanceAmount += this.balanceAmount;if (amount > balanceAmount) { this.balanceAmount = 0; // withdraw all amount from this instance throw new IllegalArgumentException( "Transfer cannot ba.displayAllAmount(be completed"); // Display the new balanceAmount in ba (may cause deadlock) } } ba.balanceAmount += }amount; } private synchronized void displayAllAmount() { this.balanceAmount -= amount; } System.out.println(balanceAmount);} } public static void initiateTransfer(final BankAccount first, final BankAccount second, final double amount) { Thread ttransfer = new Thread(new Runnable() { @Override public void run() { first.depositAllAmountdepositAmount(second, amount); } }); ttransfer.start(); } } |
Whenever a transfer occurs, the two BankAccount
objects are ordered so that the first
object's lock is acquired before the second
object's lock. Consequently, if When two threads attempt transfers between the same two accounts, they will both each try to acquire the first account's lock before acquiring the second account's lock. Consequently, with the result that one thread will acquire acquires both locks, complete completes the transfer, and release releases both locks before the other thread may can proceed.
Unlike the previous compliant solution, this solution incurs no performance penalty because permits multiple concurrent transfers can occur concurrently as long as the transfers involve distinct target accounts.
Compliant Solution (ReentrantLock
)
In this compliant solution, each BankAccount
has a java.util.concurrent.locks.ReentrantLock
associated with it. This design permits the depositAllAmountdepositAmount()
method to try acquiring to attempt to acquire the locks of both accounts' locks, but releasing to release the locks if it fails, and trying to try again later if necessary.
Code Block | ||
---|---|---|
| ||
final class BankAccount { private intdouble balanceAmount; // Total amount in bank account private final Lock lock = new ReentrantLock(); private final Random number = new Random(123L); private BankAccount(intdouble balance) { this.balanceAmount = balance; } // Deposits the amount from this object instance // to BankAccount instance argument ba private void depositAllAmountdepositAmount(BankAccount ba, double amount) throws InterruptedException { while throws InterruptedException { while (true) { if (this.lock.tryLock()) { try { if (ba.lock.tryLock()) { try { ba.balanceAmount += this.balanceAmount;if (amount > balanceAmount) { this.balanceAmount = 0;throw // withdraw all amount from this instance new IllegalArgumentException( ba.displayAllAmount(); // Display the new balanceAmount in ba "Transfer cannot be completed"); } ba.balanceAmount += amount; this.balanceAmount -= amount; break; } finally { ba.lock.unlock(); } } } finally { this.lock.unlock(); } } int n = number.nextInt(1000); int TIME = 1000 + n; // 1 second + random delay to prevent livelock Thread.sleep(TIME); } } privatepublic static void displayAllAmount() throws InterruptedExceptioninitiateTransfer(final BankAccount first, final BankAccount second, final double amount) { while (trueThread transfer = new Thread(new Runnable() { if public void run(lock.tryLock()) { try { System.out.println(balanceAmount first.depositAmount(second, amount); break; } catch (InterruptedException e) { } finally { lock.unlockThread.currentThread().interrupt(); // Reset interrupted status } } int n = number.nextInt(1000); } }); int TIME = 1000 + n; // 1 second + random delay to prevent livelock Thread.sleep(TIME); } } public static void initiateTransfer(final BankAccount first, final BankAccount second) { Thread t = new Thread(new Runnable() { public void run() { try { first.depositAllAmount(second); } catch (InterruptedException e) { Thread.currentThread().interrupt(); // Reset interrupted status } } }); t.start(); } } transfer.start(); } } |
Deadlock is impossible in this compliant solution because no method grabs a lock and holds it locks are never held indefinitely. If the current object's lock is acquired , but the the second lock is unavailable, the first lock is released and the thread sleeps for some specified amount of time before retryingattempting to reacquire the lock.
Code that uses this lock behaves locking strategy has behavior similar to that of synchronized code that uses the traditional monitor lock. ReentrantLock
also provides several other capabilities. For example, for instance, the tryLock()
method does not block waiting if immediately returns false when another thread is already holding holds the lock. The class Further, the java.util.concurrent.locks.ReentrantReadWriteLock
can be used when some thread requires class has multiple-readers/single-writer semantics and is useful when some threads require a lock to write information while other threads require the lock to concurrently read the information.
Noncompliant Code Example
...
(Different Lock Orders, Recursive)
The following immutable WebRequest
class Consider an immutable class WebRequest
that encapsulates a web request to received by a server.:
Code Block |
---|
// Immutable WebRequest
public final class WebRequest {
private final long bandwidth;
private final long responseTime;
public WebRequest(long bandwidth, long responseTime) {
this.bandwidth = bandwidth;
this.responseTime = responseTime;
}
public long getBandwidth() {
return bandwidth;
}
public long getResponseTime() {
return responseTime;
}
}
|
Each request has a response time associated with it, as well as along with a measurement of the network bandwidth required to fulfill the request.
This noncompliant code example consists of an application that monitors web requests . It calculates and provides routines for calculating the average bandwidth and average response time required to service all serve incoming requests.
Code Block | ||
---|---|---|
| ||
public final class WebRequestAnalyzer { private final Vector<WebRequest> requests = new Vector<WebRequest>(); public boolean addWebRequest(WebRequest request) { // Lock on last element to prevent data race with the calculateAverageResponseTime() method new Vector<WebRequest>(); public boolean addWebRequest(WebRequest request) { return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime())); } public double getAverageBandwidth() { synchronizedif (requests.lastElementsize() == 0) { // Defensive copying throw new IllegalStateException("The vector is empty!"); } return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()))calculateAverageBandwidth(0, 0); } } public double getAverageBandwidthgetAverageResponseTime() { return calculateAverageBandwidth(0,if (requests.size() == 0); { } public double getAverageResponseTime() { throw new IllegalStateException("The vector is empty!"); } return calculateAverageResponseTime(requests.size() - 1, 0); } private double calculateAverageBandwidth(int i, long bandwidth) { if (i >== requests.size()) { return bandwidth / requests.size(); } synchronized (requests.elementAt(i)) { bandwidth += requests.get(i).getBandwidth(); return calculateAverageBandwidth(++i, bandwidth); // Acquires locks in increasing order return calculateAverageBandwidth(++i, bandwidth); } } private double calculateAverageResponseTime(int i, long responseTime) { if (i <= -1) { return responseTime / requests.size(); } synchronized (requests.elementAt(i)) { responseTime += requests.get(i).getResponseTime(); // Acquires locks in decreasing order return calculateAverageResponseTime(--i, responseTime); // Acquires locks in decreasing order } } } |
The monitoring application is built upon class WebRequestAnalyzer
that around the WebRequestAnalyzer
class, which maintains a list of web requests using vector the requests
. The vector requests
is suitably initialized after defensively copying the requests vector and includes the addWebRequest()
setter method. Any thread can get request the average bandwidth or average response time of all web requests by invoking the getAverageBandwidth()
and getAverageResponseTime()
methods.
These methods use fine-grained locking by holding locks on individual elements (web requests) of the vector. The These locks permit new requests to be added while the computations are still underway. Consequently, the statistics reported by the methods are accurate at the time when they return the results.
Unfortunately, this implementation noncompliant code example is prone to deadlock because the recursive calls within the synchronized regions of these methods acquire the intrinsic locks in opposite numerical orders. That is, calculateAverageBandwidth()
requests locks from index 0 up to requests.size()
- − 1, whereas calculateAverageResponseTime()
requests them from index requests.size()
- − 1 down to 0. Because of recursion, no previously acquired locks are never released by either method. A deadlock Deadlock occurs when two threads call these methods out of order in that, because one thread calls calculateAverageBandwidth()
, while the other calls calculateAverageResponseTime()
before either method has finished executing.
For example, if when there are 20 requests in the vector, and one thread calls getAverageBandwidth()
, it the thread acquires the intrinsic lock of WebRequest
0, the first element in the vector. Meanwhile, if a second thread calls getAverageResponseTime()
, it acquires the intrinsic lock for of WebRequest
19, the last element in the vector. Consequently, deadlock results because neither thread can acquire all of the locks and proceed with the calculationsrequired to proceed with its calculations.
Note that the addWebRequest()
method also has a race condition with calculateAverageResponseTime()
. While iterating over the vector, new elements can be added to the vector, invalidating the results of the previous computation. This race condition can be prevented by locking on the last element of the vector (when it contains at least one element) before inserting the element.
Compliant Solution
In this compliant solution, the two calculation methods acquire and release locks in the same order, beginning with the first web request in the vector. vector.
Code Block | ||
---|---|---|
| ||
public final class WebRequestAnalyzer {
private final Vector<WebRequest> requests = new Vector<WebRequest>();
public boolean addWebRequest(WebRequest request) {
return requests.add(new WebRequest(request.getBandwidth(),
request.getResponseTime()));
}
| ||
Code Block | ||
| ||
public class WebRequestAnalyzer { private final Vector<WebRequest> requests = new Vector<WebRequest>(); public booleandouble addWebRequestgetAverageBandwidth(WebRequest request) { // No need to lock on the last element because locks are acquired in increasing orderif (requests.size() == 0) { throw new IllegalStateException("The vector is empty!"); } return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime())); calculateAverageBandwidth(0, 0); } public double getAverageBandwidth() { getAverageResponseTime() { if (requests.size() == 0) { throw returnnew calculateAverageBandwidth(0, 0IllegalStateException("The vector is empty!"); } public double getAverageResponseTime() { } return calculateAverageResponseTime(0, 0); } private double calculateAverageBandwidth(int i, long bandwidth) { if (i >== requests.size()) { return bandwidth / requests.size(); } synchronized (requests.elementAt(i)) { // Acquires locks in increasing order bandwidth += requests.get(i).getBandwidth(); return calculateAverageBandwidth(++i, bandwidth); } } private double calculateAverageResponseTime(int i, long responseTime) { if (i >== requests.size()) { return responseTime / requests.size(); } synchronized (requests.elementAt(i)) { synchronized (requests.elementAt(i)) {// Acquires locks in increasing order responseTime += requests.get(i).getResponseTime(); return calculateAverageResponseTime(++i, responseTime); // Acquires locks in increasing order } } } |
Consequently, while one thread is calculating the average bandwidth or response time, another thread cannot interfere or induce a deadlock. This is because the other thread would first have to synchronize on the first WebRequest
, which is impossible until the first calculation is completeinterfere or induce deadlock. Each thread must first synchronize on the first web request, which cannot happen until any prior calculation completes.
Locking on the last element of the vector in addWebRequest()
is unnecessary for two reasons. First, the locks are acquired in increasing order in all the methods. Second, updates to the vector are reflected in the results of the computations.
Risk Assessment
Acquiring and releasing locks in the wrong order may can result in deadlocks deadlock.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
---|
CON12- J
low
likely
high
P3
L3
Automated Detection
TODO
Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the CERT website.
References
Wiki Markup |
---|
\[[JLS 05|AA. Java References#JLS 05]\] [Chapter 17, Threads and Locks|http://java.sun.com/docs/books/jls/third_edition/html/memory.html]
\[[Halloway 00|AA. Java References#Halloway 00]\]
\[[MITRE 09|AA. Java References#MITRE 09]\] [CWE ID 412|http://cwe.mitre.org/data/definitions/412.html] "Unrestricted Lock on Critical Resource" |
LCK07-J | Low | Likely | High | P3 | L3 |
Automated Detection
Some static analysis tools can detect violations of this rule.
Tool | Version | Checker | Description | ||||||
---|---|---|---|---|---|---|---|---|---|
Coverity | 7.5 | LOCK_INVERSION | Implemented | ||||||
Parasoft Jtest |
| CERT.LCK07.LORD | Ensure that nested locks are ordered correctly | ||||||
ThreadSafe |
| CCE_DL_DEADLOCK | Implemented |
Related Guidelines
CWE-833, Deadlock |
Bibliography
...
CON11-J. Do not assume that declaring an object volatile guarantees visibility of its members 11. Concurrency (CON) CON13-J. Ensure that threads are stopped cleanly