CON07-J. Ensure atomicity of thread-safe code

Thread-safety guarantees that no two threads can simultaneously access or modify some shared data. However, if two or more operations need to be performed safely, it becomes necessary to enforce atomicity. It is possible for two threads to read some shared value, independently perform operations on it and induce a race condition while storing the final result.

Programmers sometimes assume that using a thread-safe Collection does not require explicit synchronization which is a misleading thought. It follows that using a thread-safe Collection by itself does not ensure program correctness unless special care is taken to ensure that the client performs all related and independently atomic operations, as one atomic operation.

Noncompliant Code Example

This noncompliant code example comprises an ArrayList collection which is non-thread-safe by default. There is, however, a way around this drawback. Most thread-unsafe classes have a synchronized thread-safe version, for example, Collections.synchronizedList is a good substitute for ArrayList and Collections.synchronizedMap is a good alternative to HashMap. The atomicity pitfall described in the coming lines, remains to be addressed even when the particular Collection offers thread-safety benefits.

class RaceCollection implements Runnable {
  private List<InetAddress> ips = Collections.synchronizedList(new ArrayList<InetAddress>());
  
  public void addIPAddress(InetAddress ia) {
    // Validate
    ips.add(ia);
  }
  
  public void run() {
    try {
      addIPAddress(InetAddress.getLocalHost());
      InetAddress[] ia = (InetAddress[]) ips.toArray(new InetAddress[0]);      
      System.out.println("Number of IPs: " + ia.length);     
    } catch (UnknownHostException e) { /* Forward to handler */ }     		
  }
  
  public static void main(String[] args) {
    RaceCollection rc = new RaceCollection();
    for(int i = 0; i < 2; i++) {
      new Thread(rc).start();
    }	  	  
  }
}

The operations within a thread's run() method are non-atomic. That is, it is possible for the first thread to operate on data that it does not expect. This noncompliant code's output, consisting of varying array lengths, indicates a race condition between threads. In other words, the statements that are responsible for adding an IP address and printing it out are not sequentially consistent.

Compliant Solution

To eliminate the race condition, ensure atomicity by using the underlying list's lock. This can be achieved by including all statements that use the array list within a synchronized block that locks on the list. This technique is also called client-side locking [[Goetz 06]].

public void addIPAddress(InetAddress ia) { 
  synchronized(ips) { // Also synchronize this method
    // Validate
    ips.add(ia);
  }
}

public void run() {
  try {
    synchronized(ips) {
      addIPAddress(InetAddress.getLocalHost());
      ia = (InetAddress[]) ips.toArray(new InetAddress[0]);           
      System.out.println("Number of IPs: " + ia.length); 
    }
  } catch (UnknownHostException e) { /* Forward to handler */ }     		
}

This form of synchronization is preferable over method synchronization for performance reasons. The advice suggested by this guideline applies to all uses of Collection classes including the thread-safe Hashtable class. Enumerations of the objects of a Collection and iterators also require explicit synchronization on the Collection object or any single lock object.

Although expensive, CopyOnWriteArrayList and CopyOnWriteArraySet classes are sometimes used to create copies of the core Collection so that iterators do not fail with a runtime exception when some data in the Collection is modified. However, any updates to the Collection are not immediately visible to other threads. Consequently, their use is limited to boosting performance in code where the writes are fewer (or non-existent) as compared to the reads [[JavaThreads 04]]. In all other cases they must be avoided.

Compliant Solution

Composition offers more benefits as compared to the previous solution, although at the cost of a slight performance penalty (refer to OBJ07-J. Understand how a superclass can affect a subclass for details on how to implement composition).

class CompositeCollection implements Runnable {
  private List<InetAddress> ips;
 
  public CompositeCollection(List<InetAddress> list) {
    this.ips = list;
  }
  
  public synchronized void addIPAddress(InetAddress ia) {
    // Validate
    ips.add(ia);
  }

  public void run() {
    try {
      InetAddress[] ia;   
      ia = (InetAddress[]) ips.toArray(new InetAddress[0]);     
      System.out.println("Number of IPs: " + ia.length); 
    } catch (UnknownHostException e) { /* Forward to handler */ }     		
  }
}

This approach allows the CompositeCollection class to use its own intrinsic lock in a way that is completely independent of the lock of the underlying list class. Moreover, this permits the underlying collection to be thread-unsafe because the CompositeCollection wrapper prevents direct accesses to its methods by exposing its own synchronized equivalents. This approach also provides consistent locking even when the underlying list is not thread-safe or when it changes its locking policy. [[Goetz 06]]

Yet another method is to extend the base class and synchronize on the method that is desired to be atomic, however, it is not recommended because it goes against the spirit of limiting class extension ([OBJ05-J. Limit the extensibility of non-final classes and methods to only trusted subclasses]). Moreover, Goetz et al. [[Goetz 06]] cite other reasons:

Extension is more fragile than adding code directly to a class, because the implementation of the synchronization policy is now distributed over multiple, separately maintained source files. If the underlying class were to change its synchronization policy by choosing a different lock to guard its state variables, the subclass would subtly and silently break, because it no longer used the right lock to control concurrent access to the base class's state.

Noncompliant Code Example

This noncompliant code example defines a thread-unsafe KeyedCounter class. Even though the HashMap field is synchronized, the overall increment operation is not atomic. [[Lee 09]]

public class KeyedCounter {
  private Map<String, Integer> map =
    Collections.synchronizedMap(new HashMap<String, Integer>());

  public void increment(String key) {
    Integer old = map.get(key);
    int value = (old == null) ? 1 : old.intValue() + 1;
    map.put(key, value);
  }

  public Integer getCount(String key) {
    return map.get(key);
  }
}

Compliant Solution

This compliant solution declares the increment() method as synchronized to ensure atomicity. [[Lee 09]]

public class KeyedCounter {
  private Map<String,Integer> map = new HashMap<String,Integer>();
 
  public synchronized void increment(String key) {
    Integer old = map.get(key);
    int value = (old == null) ? 1 : old.intValue()+1;
    map.put(key, value);
  }

  public synchronized Integer getCount(String key) {
    return map.get(key);
  }
}

Compliant Solution

The previous compliant solution does not scale very well because a class with several synchronized methods is a potential bottleneck as far as acquiring locks is concerned and may further lead to contention or deadlock. The class ConcurrentHashMap, through a more preferable approach, provides several utility methods to perform atomic operations and is used in this compliant solution [[Lee 09]]. According to Goetz et al. [[Goetz 06]] section 5.2.1. ConcurrentHashMap:

ConcurrentHashMap, along with the other concurrent collections, further improve on the synchronized collection classes by providing iterators that do not throw ConcurrentModificationException, as a result eliminating the need to lock the collection during iteration. The iterators returned by ConcurrentHashMap are weakly consistent instead of fail-fast. A weakly consistent iterator can tolerate concurrent modification, traverses elements as they existed when the iterator was constructed, and may (but is not guaranteed to) reflect modifications to the collection after the construction of the iterator.

public class KeyedCounter {
  private final ConcurrentMap<String, AtomicInteger> map =
    new ConcurrentHashMap<String, AtomicInteger>();

  public void increment(String key) {
    AtomicInteger value = new AtomicInteger(0);
    AtomicInteger old = map.putIfAbsent(key, value);
   
    if (old != null) { 
      value = old; 
    }

    value.incrementAndGet(); // Increment the value atomically
  }

  public Integer getCount(String key) {
    AtomicInteger value = map.get(key);
    return (value == null) ? null : value.get();
  }
}

Risk Assessment

Non-atomic code can induce race conditions and affect program correctness.

Automated Detection

TODO

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

References

[[API 06]] Class Vector, Class WeakReference
[[JavaThreads 04]] 8.2 "Synchronization and Collection Classes"
[[Goetz 06]] 4.4.1. Client-side Locking, 4.4.2. Composition and 5.2.1. ConcurrentHashMap
[[Lee 09]] "Map & Compound Operation"

CON06-J. Do not defer a thread that is holding a lock      11. Concurrency (CON)      CON08-J. Do not invoke a superclass method or constructor from a synchronized region in the subclass