Skip to end of metadata
Go to start of metadata

A consistent locking policy guarantees that multiple threads cannot simultaneously access or modify shared data. When two or more operations must be performed as a single atomic operation, a consistent locking policy must be implemented using either intrinsic synchronization or java.util.concurrent utilities. In the absence of such a policy, the code is susceptible to race conditions.

When presented with a set of operations, where each is guaranteed to be atomic, it is tempting to assume that a single operation consisting of individually atomic operations is guaranteed to be collectively atomic without additional locking. Similarly, programmers might incorrectly assume that use of a thread-safe Collection is sufficient to preserve an invariant that involves the collection's elements without additional synchronization. A thread-safe class can only guarantee atomicity of its individual methods. A grouping of calls to such methods requires additional synchronization for the group.

Consider, for example, a scenario in which the standard thread-safe API lacks a single method both to find a particular person's record in a Hashtable and to update that person's payroll information. In such cases, the two method invocations must be performed atomically.

Enumerations and iterators also require either explicit synchronization on the collection object (client-side locking) or use of a private final lock object.

Compound operations on shared variables are also non-atomic (see VNA02-J. Ensure that compound operations on shared variables are atomic for more information).

VNA04-J. Ensure that calls to chained methods are atomic describes a specialized case of this rule.

Noncompliant Code Example (AtomicReference)

This noncompliant code example wraps references to BigInteger objects within thread-safe AtomicReference objects:

final class Adder {
  private final AtomicReference<BigInteger> first;
  private final AtomicReference<BigInteger> second;

  public Adder(BigInteger f, BigInteger s) {
    first  = new AtomicReference<BigInteger>(f);
    second = new AtomicReference<BigInteger>(s);
  }

  public void update(BigInteger f, BigInteger s) { // Unsafe
    first.set(f);
    second.set(s);
  }

  public BigInteger add() { // Unsafe
    return first.get().add(second.get());
  }
}

AtomicReference is an object reference that can be updated atomically. However, operations that combine more than one atomic reference are non-atomic. In this noncompliant code example, one thread may call update() while a second thread may call add(). This might cause the add() method to add the new value of first to the old value of second, yielding an erroneous result.

Compliant Solution (Method Synchronization)

This compliant solution declares the update() and add() methods synchronized to guarantee atomicity:

final class Adder {
  // ...
  private final AtomicReference<BigInteger> first;
  private final AtomicReference<BigInteger> second;

  public Adder(BigInteger f, BigInteger s) {
    first  = new AtomicReference<BigInteger>(f);
    second = new AtomicReference<BigInteger>(s);
  }



  public synchronized void update(BigInteger f, BigInteger s){
    first.set(f);
    second.set(s);
  }

  public synchronized BigInteger add() {
    return first.get().add(second.get());
  }
}

Noncompliant Code Example (synchronizedList())

This noncompliant code example uses a java.util.ArrayList<E> collection, which is not thread-safe. However, the example uses Collections.synchronizedList as a synchronization wrapper for the ArrayList. It subsequently uses an array, rather than an iterator, to iterate over the ArrayList to avoid a ConcurrentModificationException.

final class IPHolder {
  private final List<InetAddress> ips = 
      Collections.synchronizedList(new ArrayList<InetAddress>());

  public void addAndPrintIPAddresses(InetAddress address) {
    ips.add(address);
    InetAddress[] addressCopy = 
        (InetAddress[]) ips.toArray(new InetAddress[0]);
    // Iterate through array addressCopy ...
  }
}

Individually, the add() and toArray() collection methods are atomic. However, when called in succession (as shown in the addAndPrintIPAddresses() method), there is no guarantee that the combined operation is atomic. The addAndPrintIPAddresses() method contains a race condition that allows one thread to add to the list and a second thread to race in and modify the list before the first thread completes. Consequently, the addressCopy array may contain more IP addresses than expected.

Compliant Solution (Synchronized Block)

The race condition can be eliminated by synchronizing on the underlying list's lock. This compliant solution encapsulates all references to the array list within synchronized blocks:

final class IPHolder {
  private final List<InetAddress> ips = 
      Collections.synchronizedList(new ArrayList<InetAddress>());

  public void addAndPrintIPAddresses(InetAddress address) {
    synchronized (ips) {
      ips.add(address);
      InetAddress[] addressCopy = 
          (InetAddress[]) ips.toArray(new InetAddress[0]);
      // Iterate through array addressCopy ...
    }
  }
}

This technique is also called client-side locking [Goetz 2006] because the class holds a lock on an object that might be accessible to other classes. Client-side locking is not always an appropriate strategy (see LCK11-J. Avoid client-side locking when using classes that do not commit to their locking strategy for more information).

This code does not violate LCK04-J. Do not synchronize on a collection view if the backing collection is accessible because, although it synchronizes on a collection view (the synchronizedList result), the backing collection is inaccessible and consequently cannot be modified by any code.

Note that this compliant solution does not actually use the synchronization offered by Collections.synchronizedList(). If no other code in this solution used it, it could be eliminated.

Noncompliant Code Example (synchronizedMap())

This noncompliant code example defines the KeyedCounter class that is not thread-safe. Although the HashMap is wrapped in a synchronizedMap(), the overall increment operation is not atomic [Lee 2009].

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

  public void increment(String key) {
    Integer old = map.get(key);
    int oldValue = (old == null) ? 0 : old.intValue();
    if (oldValue == Integer.MAX_VALUE) {
      throw new ArithmeticException("Out of range");
    }
    map.put( key, oldValue + 1);
  }

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

Compliant Solution (Synchronization)

This compliant solution ensures atomicity by using an internal private lock object to synchronize the statements of the increment() and getCount() methods:

final class KeyedCounter {
  private final Map<String, Integer> map =
      new HashMap<String, Integer>();
  private final Object lock = new Object();

  public void increment(String key) {
    synchronized (lock) {
      Integer old = map.get(key);
      int oldValue = (old == null) ? 0 : old.intValue();
      if (oldValue == Integer.MAX_VALUE) {
        throw new ArithmeticException("Out of range");
      }
      map.put(key, oldValue + 1);
    }
  }

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

This compliant solution avoids using Collections.synchronizedMap() because locking on the unsynchronized map provides sufficient thread-safety for this application. LCK04-J. Do not synchronize on a collection view if the backing collection is accessible provides more information about synchronizing on synchronizedMap() objects.

Compliant Solution (ConcurrentHashMap)

The previous compliant solution is safe for multithreaded use but does not scale because of excessive synchronization, which can lead to decreased performance.

The ConcurrentHashMap class used in this compliant solution provides several utility methods for performing atomic operations and is often a good choice for algorithms that must scale [Lee 2009].

Note that this compliant solution still requires synchronization, because without it, the test to prevent overflow and the increment will not happen atomically, so two threads calling increment() can still cause overflow. The synchronization block is smaller and does not include the lookup or addition of new values, so it has less impact on performance than the previous compliant solution.

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

  public void increment(String key) {
    AtomicInteger value = new AtomicInteger();
    AtomicInteger old = map.putIfAbsent(key, value);

    if (old != null) {
      value = old;
    }

    synchronized (lock) {
      if (value.get() == Integer.MAX_VALUE) {
        throw new ArithmeticException("Out of range");
      }
      value.incrementAndGet(); // Increment the value atomically
    }
  }

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

  // Other accessors ...
}

According to Section 5.2.1., "ConcurrentHashMap," of the work of Goetz and colleagues [Goetz 2006]:

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.

Note that methods such as ConcurrentHashMap.size() and ConcurrentHashMap.isEmpty() are allowed to return an approximate result for performance reasons. Code should avoid relying on these return values when exact results are required.

Risk Assessment

Failure to ensure the atomicity of two or more operations that must be performed as a single atomic operation can result in race conditions in multithreaded applications.

Rule

Severity

Likelihood

Remediation Cost

Priority

Level

VNA03-J

Low

Probable

Medium

P4

L3

Automated Detection

Some static analysis tools are capable of detecting violations of this rule.

ToolVersionCheckerDescription
CodeSonar4.2FB.MT_CORRECTNESS.IS2_INCONSISTENT_SYNC
FB.MT_CORRECTNESS.IS_FIELD_NOT_GUARDED
FB.MT_CORRECTNESS.STCAL_INVOKE_ON_STATIC_CALENDAR_INSTANCE
FB.MT_CORRECTNESS.STCAL_INVOKE_ON_STATIC_DATE_FORMAT_INSTANCE
FB.MT_CORRECTNESS.STCAL_STATIC_CALENDAR_INSTANCE
FB.MT_CORRECTNESS.STCAL_STATIC_SIMPLE_DATE_FORMAT_INSTANCE
Inconsistent synchronization
Field not guarded against concurrent access
Call to static Calendar
Call to static DateFormat
Static Calendar field
Static DateFormat
Coverity7.5

ATOMICITY
GUARDED_BY_VIOLATION
INDIRECT_GUARDED_BY_VIOLATION
NON_STATIC_GUARDING_STATIC
NON_STATIC_GUARDING_STATIC
FB.IS2_INCONSISTENT_SYNC
FB.IS_FIELD_NOT_GUARDED
FB.IS_INCONSISTENT_SYNC
FB.STCAL_INVOKE_ON_STATIC_ CALENDAR_INSTANCE
FB.STCAL_INVOKE_ON_STATIC_ DATE_FORMAT_INSTANCE
FB.STCAL_STATIC_CALENDAR_ INSTANCE
FB.STCAL_STATIC_SIMPLE_DATE_ FORMAT_INSTANCE

Implemented
Parasoft Jtest 10.3 TRS.SSUG, TRS.MRAVImplemented
ThreadSafe1.3

CCE_CC_NON_ATOMIC_GCP
CCE_CC_NON_ATOMIC_CP
CCE_CC_UNSAFE_ITERATION
CCE_LK_REPLACE_WITH_TRYLOCK

Implemented

Related Guidelines

MITRE CWE

CWE-362, Concurrent Execution Using Shared Resource with Improper Synchronization ("Race Condition")
CWE-366, Race Condition within a Thread
CWE-662, Improper Synchronization

Bibliography

[API 2014]

 

[Goetz 2006]

Section 4.4.1, "Client-side Locking"
Section 5.2.1, "ConcurrentHashMap"

[JavaThreads 2004]

Section 8.2, Synchronization and Collection Classes

[Lee 2009]

Map & Compound Operation

 


32 Comments

  1. I am curious as to the relation of CON07-J and CON01-J. It seems CON07-J pertains to thread-safe code on non-primitive data and CON01-J pertains to non-atomic operations on primitive data. Perhaps these two should be merged?

    One note on code samples. I think all NCCEs & CSs should have 'nicknames' next to them (unless there is only one NCCE & one CS). That way we can identify each one easily. For instance, the first 3 NCCE's here, I would nickname synchronizedList, subclass, synchronized methods. And the first two CS's, I would name 'synchronized list' and 'composite collection'. You can use idfferent nicknames if you like, but the code samples here definitely need 'em for identification.

    • Why the 2nd NCCE? This rule is about atomicity of thread-safe code, and the 2nd NCCE is bad b/c it violates OBJ05-J. The only good reason I see to leave this NCCE in is if you have a historical instance (eg some historical vul occurred b/c someone made this same mistake.)
    • The third NCCE is a good idea, but the code currently makes it impossible for an outside class to have access to the ips. (This is easy to solve with a getter method). As it is currently defined, the code is secure.
    • For the third CS, I would take the doSomething() method out of the CompositeCollection class, since the class is a 'new' class, unique to the last CS. Leave doSomething() in a Helper class, or (for illustration purposes) leave it outside any class at all.)
    1. CON07 and CON01 have been separated even though the central idea is to use synchronization for atomicity. The underlying concept behind this guideline is:

      • to break the notion that multiple operations on thread-safe API classes are atomic and therefore safe (as some developers mistakenly assume).
      • to answer the question - how will you extend the standard API to add thread-safe methods?

      CON01 does not deal with the standard API but thread-unsafety "in the field".

      I've specified the nick-names. Thanks.

      • The motivation behind the 2nd NCE (Subclass) is to show that it is not a good idea to extend a thread-safe class to add another thread-safe custom method and try to roll out your own API. We've had this discussion somewhere else on the wiki too (IIRC wrt subclassing BigInteger) and the conclusion was to avoid defining your own API.
      • Ah, yes. I've changed the accessibility of the list to public. I need to remind myself time and again not to write secure code in NCEs!
      • I don't follow this point. Moving doSomething() outside the CompositeCollection class would defeat the purpose of composition and the CS. Can you elaborate please? Thanks.
      1. CON07 and CON01 have been separated even though the central idea is to use synchronization for atomicity. The underlying concept behind this guideline is:
        ...

        I don't understand the distinction. Maybe I'm just focusing on atomicity. But reading the two rules, I see this one is about atomity for 'non-primitive' API methods, and CON01-J is about guaranteeing atomicity for primitive types and operators, particularly --.

        • The motivation behind the 2nd NCE (Subclass) is to show that it is not a good idea to extend a thread-safe class to add another thread-safe custom method and try to roll out your own API. We've had this discussion somewhere else on the wiki too (IIRC wrt subclassing BigInteger) and the conclusion was to avoid defining your own API.

        I guess the problem is that this NCCE basically belongs in OBJ05-J. The concurrency aspect adds nothing. There is no text in the NCCE that indicates that concurrency is at all relevant to the OBJ05-J violation.

        • Ah, yes. I've changed the accessibility of the list to public. I need to remind myself time and again not to write secure code in NCEs!

        Bzzzt. Now your NCCE violates OBJ00-J. Declare data members as private and provide accessible wrapper methods. Keep those reminders in mind. You want your NCCEs to abide by every secure coding rule (except the one containing it).

        • I don't follow this point. Moving doSomething() outside the CompositeCollection class would defeat the purpose of composition and the CS. Can you elaborate please? Thanks.

        I thought the idea of the CS is that you are adding a new CompositeCollection class which encapsulates access to the ips list, and guarantees atomicity. The doSomething() method requires the atomicity & encapsulation, but does not provide any. Furthermore, it is obviously part of some other code (eg the Helper class in the other code samples.) That's why I think it should go outside the CompositeCollection class. (This is more of a style guideline than a correctness guideline, as the current CS is correct.)

          • Regarding the distinction, you are right on part A. Part B is the second paragraph.
          • The subclass NCE is still important as stated in the quote from [Goetz 06]. Changes in locking policies can silently break the subclass locking. This is a security problem that is concurrency related.
          • I think an NCE can violate multiple rules provided I state so explicitly which I have now.
          • "The doSomething() method requires the atomicity & encapsulation, but does not provide any." Why not? It uses intrinsic synchronization. It is also not required to be part of some other code. We have to find a place to insert this method, that's all. All we are trying is to add a custom method doSomething() that is thread-safe and does not exist in the standard thread-safe API for the list class. The current CS uses a composition approach which is different from all approaches discussed so far. I'll try to explain this better in the text if it's not intuitive.
            • Regarding the distinction, you are right on part A. Part B is the second paragraph.

            You are referring to the paragraph that discusses the fallacy of assuming a thread-safe collection does not requir eexplicit synchronization. I hold that the same fallacy applies to CON01-J, where the fallacy there is assuming that operators like -- are atomic, when they really aren't.

            • The subclass NCE is still important as stated in the quote from Goetz 06. Changes in locking policies can silently break the subclass locking. This is a security problem that is concurrency related.

            OK, but then it sounds like it belongs in a rule about concurrency and subclassing, or in a rule by itself.

            • I think an NCE can violate multiple rules provided I state so explicitly which I have now.

            Agreed. This discussion dovetails into the one at TSM03-J. Do not publish partially initialized objects, which we need not repeat here.

            • "The doSomething() method requires the atomicity & encapsulation, but does not provide any." Why not? It uses intrinsic synchronization.

            It provides no thread-safety by not employing any thread APIs (synchronized, volatile, etc). And it reads ips only once, which is guaranteed atomic in the CS, since it is synchronized. All the intelligence wrt concurrency is encapsulated in the CompositeCollection class, with the doSomething() method has and needs none. In any real code the doSomething() method will belong to some class, (and should have a better name, too).

            Let me make a suggestion. Try changing the name from doSomething() to a name more appropriate for what the code must do...once you know a good name for this snippet of code, the choice of what class it goes into should become obvious. For instance, I would call it printIPAddress(), and with that name, it clearly belongs outside the CompositeCollection class.

              • Agreed; generally the same fallacies apply. This is part A. Part B is that CON00 is about API design and this guideline is about extending a published API when you want to provide a thread-safe method. And the latter part is the central focus. Combining CON00 and this guideline will result in a mammoth-guideline and exacerbate this confusion.
              • The subclass case fits well here; nevertheless it can be added as a separate guideline.
              • I've added a missing line to doSomething() that adds the IP address. Perhaps this was the source of the confusion. Even without this, the toArray() and printing must be done atomically.
                • The method synchronization NCCE is a NCCE but not b/c it synchronizes on the wrong object. It is bad because it provides access to the ips object. If you leave ips private and provide a synchronized getter() method, then other threads can modify ips directly and cause race conditions. And this remains true even if the methods are syncronized on ips rather than the this object. Finally, leaving ips private makes your NCCE compliant with OBJ00-J. This also affects the two subsequent CS's.
                • WRT the Subclass NCCE, isn't there another concurrency rule that discusses overriding non-synchronized methods with synchronized ones? Perhaps CON09-J? I just think this is a whole 'nother can of worms that deserves more attention than this rule can give it.
                • OK, I think you may win the last point. If addAndPrintIP() must be atomic on ips, then I agree it should be part of the CompositeCollection class. (I was previously assuming you get the array via toArray, and then your function needs no atomicity. I'm not sure if toArray() would copy the elements from a list; if it does not, you need atomicity during the print statement.)
                  • It is bad because it syncs on the wrong object and also violates OBJ04. It is true that it should violate another guideline to be unsafe but it doesn't mean it is synchronizing correctly. The idea about accessibility of the object is sometimes made independently regardless of whether the code will be used in a multi-threaded context. Note that package-private is usually good enough but it still doesn't make this code secure from the pov of trusted code in the same package (that does something concurrently).
                  • Yes. But in this case we are not overriding an existing method but rolling out our own. As I pointed out, this can be discussed elsewhere too.
  2. The public/private nature of ips is inconsistent in the NCCEs. It should be private, perhaps with a protected getIps() method for the 2nd NCCE.

    Last year I made ramblings that this rule should be merged with CON01-J...not sure what the conclusion was. Here's what I surmise. Both rules have good NCCE/CS's, but the titles are not helpful.

    • CON01-J: The first NCCE/CS set demonstrates that 'volatile' does not guarantee atomicity on composite functions on fields (eg ++)
    • CON01-J: The second NCCE/CS demonstrates that functions using multiple atomic object references is not atomic w/o extra locking.
    • CON07-J: The first NCCE/CS set demonstrates that composition of elements (in an array) is not atomic w/o extra locking.
    • CON07-J: The soecond NCCE/CS set demonstrates that composition of elements (in a hashtable) is not atomic w/o extra locking.

    Currently I think its all right to leave these rules separate, as long as they xref each other. CON01-J is about atomicitity of primitive fields/references and CON07-J is about atomicity of collections.

    1. Simply put, CON01 is about thread-safe API design and CON07 is about using and extending existing thread-safe APIs correctly. The motivation for the latter was to break the misconception "I am using a thread-safe class so whatever operations I will do are atomic as a whole". Intermediate programmers probably know all this, however, they may benefit from the "extending the existing API" part.

      1. First, I bet intermediate programmers don't know this deep down.

        That point aside, I still feel that your distinction applies to both rules. CON01 warns against relying on the 'thread-safety' of primitive types, and CON07 warns against relying on the thread-safety of classes that promise some thread-safety. The misconception is important to quash, but that could be done by just one rule.

        I should also mention CON25-J which warns against relying on the thread-safety of 64-bit values.

        I'm beginning to think we should move the 2nd NCCE/CS from CON01 to CON07 since it also deals with objects. Then CON07 becomes the general 'composite functions' does not provide atomicity' rule, while CON01 becomes specific warning that ++ and – are really 'composed functions'.

        1. We could do this in one rule, but it will then talk about several issues which is more likely to confuse things:
          1. Designing thread-safe APIs and pitfalls of volatile. Throw in some sequential consistency too.
          2. Extending existing thread-safe classes
          3. Quashing the misconception - composite operations on thread-safe classes are atomic

          I think CON01 and CON07 could be next to one another in the final order of the guidelines. (hb(CON01, CON07)).

          Referring CON25 everywhere is a bit questionable because most of the time, this issue does not manifest. This is not a great yardstick but most programmers don't have to deal with it.

          The 2nd NCE/CS from CON01 can be used here because in theory AtomicReference is a class that already exists. But according to convention we choose to treat them akin to "atomic variables". I won't say that CON01 is only about primitive types and operations on them. It would be acceptable to have an NCE/CS with object fields in CON01. Note that this still differs from CON07 because we are designing the API as opposed to extending a pre-existing one. Consider for example, the Compliant Solution (thread-safe composition) in CON26. It violates CON07 and not CON01 (see my last comment there).

          1. My impressions so far is that the distinction between CON01 to CON07 is completely artificial, and that these should probably be combined as one guideline, most likely CON01. BTW, (hb(CON01, CON07)) is already true in the current ordering. 8^)

            I don't even agree with David's comment that we should break out increment and decrement from other compound operations. This just reinforces misconceptions that these operations are somehow different (e.g., atomic). I would certainly use these as an example of compound operations.

            I'll investigate further, but this rule is highly inaccurate, and trying to maintain a nonsensical distinction between these two guidelines will result in both of them being unusable.

            1. In CON01 we largely wanted detectors to catch misuse of volatile for composite operations. CON07 says that independently synchronized calls are not atomic when considered as a group (volatile doesn't come into the picture). The solution happens to be the same. But won't detectors want to treat the violations separately? If we choose to combine them, the introduction from this guideline also ought to go somewhere. My fear was including too much information together in CON01.

  3. The real problem was that I accidentally copied the last CS into the previous CS in version 96. David then changed the description of the copied CS because the previous one didn't match. We both failed to realize that the examples in both CSs were the same. I've tried to revert to the original. In the process, I discovered a null ptr exception in the last CS's getCount() method and while fixing it I realized it is no longer atomic. So I am removing the draft-one tag from this guideline until this is sorted out.

  4. I still think this paragraph can be clearer:

    Even though the Collection wrapper offers thread-safety guarantees for individual method invocations, a sequence of method calls is not atomic. For example, when multiple threads invoke the addAndPrintIPAddresses() method to add an IP address and iterate over the array addressCopy, each thread can observe addressCopy to contain a different number of IP addresses because of the race condition in the addAndPrintIPAddresses() method.

    Maybe we can talk about this later today.

  5. The Automated Detection is not complete. It's marked TODO.

    1. I like the fact that this sentence was reworded:

      See VNA02-J. Ensure that compound operations on shared variables are atomic for more information.

      to:

      For more information, see VNA02-J. Ensure that compound operations on shared variables are atomic.

      Increases readability because the link is pushed back. It might be a good idea to do this where possible.

    • The sentence "An array, rather than an iterator, is used to iterate over Arraylist to avoid a ConcurrentModificationException."

    sounds a little odd because arrays and iterators cannot be compared.

    "Iterations are performed on an array that contains a copy of the ArrayList, to avoid a ConcurrentModificationException."

    Arraylist should also be Array*L*ist.

    • Can we move the link to the guideline to the end of the sentence? For example,

    "LCK04-J. Do not synchronize on a collection view if the backing collection is accessible provides more information about synchronizing on synchronizedMap objects"

    to :

    "More information about synchronizing on synchronizedMap objects can be found in LCK04-J. Do not synchronize on a collection view if the backing collection is accessible".

    and

    "For more information, see INT00-J. Perform explicit range checking to ensure integer operations do not overflow"

  6. Might want a ConcurrentMap example that uses a cas-loop instead of AtomicInteger:

    final class KeyedCounter {
      private final ConcurrentMap<String, Integer> map =
        new ConcurrentHashMap<String, Integer>();
    
      public void increment(String key) {
        Integer old = map.putIfAbsent(key, 1);
    
        if (old == null) {
          return;
        }
    
        for (;;) {
           if (old == Integer.MAX_VALUE) {
             throw new ArithmeticException("Out of range");
           }
    
           if (map.replace(key, old, old + 1)) {
             break;
           }
    
           old = value.get(); // careful not to unbox here!
         }
      }
    
      public Integer getCount(String key) {
        return map.get(key);
      }
      // Other accessors ...
    }
    

    Also, no need to cast after calling Collection.toArray.

  7. What is "invariant" or "invariant involving multiple objects"? If you could express the same idea without using these term, I think it easier to be understood.

    1. 'Invariant' is a CS technical term...some property that is not made explicit in the code, but is known to be true and the program requires it to be true in order to function. For instance, suppose you use an array of ints to store a bunch of sizes of memory blocks. That array would have the invariant that all values are nonnegative, but that may not ever be explicitly mentioned in the code. Perhaps we should add it to the Definitions section?

      1. Thanks for the clarification, David. Yes, adding the term to the Definitions section definitely helps!

  8. I added some words to make explicit the meaning of the sentence

    A grouping of calls to such methods requires additional synchronization.

    Adding "for the group",

    A grouping of calls to such methods requires additional synchronization for the group.

  9. In the following sentence:

    Given an invariant involving multiple objects, a programmer might incorrectly assume that a group of individually atomic operations is collectively atomic without additional locking.

    It's hard to understand why an invariant on "multiple objects" is significant. Also the connection between multiple objects and individually atomic operations.

    1. Agreed, I rewrote that sentence. (The 'invariant' was supposed to refer to the atomicity of individual operations.)

  10. In the ConcurrentHashMap example as it is the overflow test and the increment operation are not done atomically. If two threads pass the test before the first increments while the value equals (Integer.MAX_VALUE - 1), both threads will increment thus causing an undetected overflow.

    1. I've fixed this by adding a synchronized block around the check and increment parts of the code. Sigh. This negates some of the performance improvement of using ConcurrentHashMap, but IMHO not all.

      1. Yes, it would be better to use the CAS support of AtomicInteger:

        int cur = value.get();
        while(true) {
          if(cur == Integer.MAX_VALUE) { throw ... }
          if(value.compareAndSet(cur, cur+1)) {
            break;
          }
          cur = value.get();
        }
  11. When using a ConcurrentMap and putIfAbsent, if cache hits are expected to outweigh cache misses (which is probably the common case, otherwise, why use a map in the first place?), then this is a better pattern:

     

    AtomicInteger value = map.get(key);
    if(value == null) {
      value = new AtomicInteger();
      AtomicInteger curValue = map.put(key, value);
      if(curValue != null) {
        value = cureValue;
      }
    }   
  12. didn't see this as a resource exhaustion attack so I removed the label.