Pure Danger Tech


navigation
home

Java Concurrency Bugs #5: inconsistent synchronization

13 May 2009

A classic Java concurrency bug that you still see pop up frequently is inconsistent synchronization. The Java Memory Model defines the semantics that a Java programmer can expect in a *properly synchronized program*. The JMM specifies that a write made under synchronization will be visible to a subsequent read under synchronization on the same monitor. A subsequent read NOT under synchronization has no such guarantees.

Typically this shows up in code where an attribute is written under synchronized but read without it:

public class Broken {
  private int value;
  public synchronized void setValue(int value) {
    this.value = value;
  }
  public int getValue() {
    return this.value;
  }
}

If one thread calls setValue() there is no guarantee that subsequent reads in other threads via getValue() will ever see that value. Probably the most common version of this I’ve run across (and ok, written myself) is with a HashMap:

public class SomeData {
  private final Map data = new HashMap();

  public void set(String key, String value) {
    synchronized(data) {
      data.put(key, value);
    }
  }

  public String get(String key) {
    return data.get(key);
  }
}

This is exactly the same problem – set() is synchronized, get() is not. However, HashMap has a far more insidious problem than the simple integer above. Hash map gets are only ~O(1) when the number of internal bucket collisions in the map is constrained (worst case, it devolves into a linked list at O(n)). To address this problem, HashMap uses the size and load factor to determine when it needs to rehash. A rehash causes new buckets to be created and all entries to be assigned to a new bucket by re-evaluating the hash function. And this is where the problem comes in with HashMap.get():

public V get(Object key) {
	if (key == null)
	    return getForNullKey();

        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {

            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

You’ll notice that get() contains a loop that walks through the collision list in a bucket. It’s entirely possible if you are reading this list while a rehash occurs that you can hit the termination condition for the loop incorrectly and miss the value. Older versions of this code contained a while(true) {} loop that could actually trigger an infinite loop. I’m not sure that’s possible in this newer version but in any case you can certainly get incorrect results from get().

One exception case for unsynchronized gets on a HashMap is with a read-only Map created during construction. In this case, you are subject to final field freeze semantics. These guarantee that if you declare the HashMap field as final, fill the map during construction, never modify that map or those objects after that, and safely publish the object, then all threads that subsequently read from the map are guaranteed to see the values in the map, even without synchronization.

An example:

public class Stooges { 
    private final Map stooges = new HashMap();

    public Stooges() {
        stooges.put("Larry", "Fine");
        stooges.put("Curly", "Howard");
        stooges.put("Moe", "Howard");
    }

    // This is safe (as long as stooges can't be modified elsewhere)
    public String getStoogeLastName(String name) {
        return stooges.get(name);
    }
}

Previous concurrency bug articles: Poll#1#2#3#4

PS. I should make a blatant plug here for two Java concurrency things. First, I’ve written a Java concurrency refcard for Dzone that is currently in editing and should be out in June (free as with all refcards). I spent a lot of time on it and I’m pretty proud with how the content turned out (many many thanks to those who sent ideas and suggestions on Twitter).

Second, I’ll be doing a talk at JavaOne on Java concurrency bugs like the one above. If you happen to be going to JavaOne, check it out!