Java Concurrency Bugs #5: inconsistent synchronization

11

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!

Comments

11 Responses to “Java Concurrency Bugs #5: inconsistent synchronization”
  1. Hi Alex,

    In the first example of Broken class I think that if you declared instance variable like: private volatile int value; would solve the problem, right? Even if the read is not synchronized each thread will see the most up-to-date value. Without either synchronization or flagging this variable as volatile, you can’t be even sure that the threads will see any changes to this variable because threads may create local caches.

    I’m not sure how that would work with map though…

    Cheers!
    Przemek

  2. Alex says:

    @Przemek: Yep, volatile would be sufficient for the int example but wouldn’t help you at all with the Map.

  3. Michael B says:

    Call me an idiot but isn’t this a programmer error as opposed to a bug? Yes it might lead to a bug in the program that you are creating but there’s nothing wrong with java itself.

  4. @Przemek – Yes, but I think AtomicInteger is a better abstraction for this sort of thing… for one it’s an actual abstraction not just a magical keyword! Knowing the Atomic* libraries has been really helpful for me.

    IntelliJ IDEA has inspections for this issue called “Field accessed in both synchronized and unsynchronized contexts. Do you know if FindBugs or some other analysis tool can do the same?

  5. Alex says:

    @Michael B: Yes, this series is about programmer errors ie bugs. I’m not trying to suggest anything is wrong with Java. Not sure how you got that idea?

    @Hamlet: I totally intended but forgot to mention that FindBugs does indeed have detectors (the IS Inconsistent Synchronization detector in fact). It checks for all accesses to a field in a class and whether it’s done in or out of synchronization. The detector actually uses some heuristics to decide whether this is actually a bug to avoid false positives so it will miss some cases.

  6. Anonymous says:

    Is it guaranteed that the code in the last example is thread-safe? Should not we first populate the map and only then assign it to the field?

  7. Anton says:

    Is it guaranteed that the code in the last example is thread-safe? Should not we first populate the map and only then assign it to the field?

    Sorry, didn’t sign the first one

  8. Alex says:

    @Anton: The last example is thread-safe. No other thread can see the map until construction completes and at the end of construction final field freeze occurs such that other threads that get this instance of Stooges are guaranteed to see all objects reachable from stooges at the time of freeze, even without synchronization.

    You don’t need to delay assignment because no one else can see the field. You should consider subclasses though which will have access to the field during their own construction and they could unsafely publish the map or “this”, ruining the semantics we’re trying to achieve. You could address that by moving the field initialization into the constructor or making the class final.

  9. Anonymous says:

    @Michael B: Yes, this series is about programmer errors ie bugs. I’m not trying to suggest anything is wrong with Java. Not sure how you got that idea?

    Sorry spend too much time with ppl who think they found bugs while it’s just there lack of understanding, guess it made me ‘twitchy’.

  10. Matias says:

    Hi Alex,

    I have read your article on Inconsistent synchronization. Using the FindBugs tool version 1.39, published 5000 cases under this heading. The majority of them located within the implementation of the VO’s. Analyzing the code generated in these implementations is noted that like implements the methods of the class also implements the equals method. The strange thing is that the class definition and the method in question is generated by AndroMDA, that is self-generating the code under discussion. The peculiarity here is that the equals method is synchronized. Therefore FindBugs detected in the methods of the class itself is not synchronized reading while the equals method if that synchronizes access to them.

    Two questions:

    Any idea because the equals method is synchronized?
    Under your view that there is such a problem is detected FindBugs?

    Excuse my poor English and thank you.

  11. Alex says:

    @Matias: I think I understand what you’re describing. As to whether it is the equals() method or the other methods that are correct, that’s really hard for me to say without a lot more context about usage of these objects. If the other generated methods can be accessed from multiple threads, then I would say they are broken without synchronization and FindBugs is correctly detecting a bug. Sounds like the fix in this case might be in AndroMDA.

    Alternately, it could be that AndroMDA is proactively (and incorrectly) generating equals() methods as synchronized. If these objects are used purely in a thread-confined way, then that synchronization seems unnecessary and again the fix seems like it should be in AndroMDA to not generate the synchronized on equals().