Concurrent Modification Exception

Question

I'm currently working on a multi-threaded application, and I occasionally receive a concurrently modification exception (approximately once or twice an hour on average, but occurring at seemingly random intervals).

The faulty class is essentially a wrapper for a map -- which extends LinkedHashMap (with accessOrder set to true). The class has a few methods:

synchronized set(SomeKey key, SomeValue val)

The set method adds a key/value pair to the internal map, and is protected by the synchronized keyword.

synchronized get(SomeKey key)

The get method returns the value based on the input key.

rebuild()

The internal map is rebuilt once in a while (~every 2 minutes, intervals do not match up with the exceptions). The rebuild method essentially rebuilds the values based on their keys. Since rebuild() is fairly expensive, I did not put a synchronized keyword on the method. Instead, I am doing:

public void rebuild(){
  /* initialization stuff */
  List<SomeKey> keysCopy = new ArrayList<SomeKey>();
  synchronized (this) {
    keysCopy.addAll(internalMap.keySet());
  }
  /* 
    do stuff with keysCopy, update a temporary map
   */    
  synchronized (this) {
    internalMap.putAll(tempMap);
  }
}

The exception occurs at

keysCopy.addAll(internalMap.keySet());

Inside the synchronized block.

Suggestions are greatly appreciated. Feel free to point me to specific pages/chapters in Effective Java and/or Concurrency in Practice.

Update 1:

Sanitized stacktrace:

java.util.ConcurrentModificationException
        at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(LinkedHashMap.java:365)
        at java.util.LinkedHashMap$KeyIterator.next(LinkedHashMap.java:376)
        at java.util.AbstractCollection.toArray(AbstractCollection.java:126)
        at java.util.ArrayList.addAll(ArrayList.java:473)
        at a.b.c.etc.SomeWrapper.rebuild(SomeWraper.java:109)
        at a.b.c.etc.SomeCaller.updateCache(SomeCaller.java:421)
        ...

Update 2:

Thanks everyone for the answers so far. I think the problem lies within the LinkedHashMap and its accessOrder attribute, although I am not entirely certain atm (investigating).

If accessOrder on a LinkedHashMap is set to true, and I access its keySet then proceed to add the keySet to a linkedList via addAll, do either of these actions mutate the order (i.e. count towards an "access")?

Answer 1

Try removing the synchronized keyword from the set() and get() methods, and instead use a synchronized block inside the method, locking on internalMap; then change the synchronized blocks on the rebuild() method to lock on the internalMap as well.

Answer 2

Are those all function you have in your wrapper? Because this exception could be thrown while you somehow iterating over collection in another place. And I guess you synchronized method with potential obvious race condition, but probably have missed less obvious cases. Here the reference to exception class docs.

Answer 3

that is strange. I cant see any way that the exception is being thrown at the location you are identifying (in the default implmentation in Java 6). are you getting a ConcurrentModificationException in the ArrayList or the HashMap? have you overridden the keySet() method in your HashMap?

edit my mistake - the ArrayList will force the KeySet to iterate (AbstractCollection.toArray() will iterate over its keys)

there is somewhere in the code that is allowing you to update your internal map that is not synchronized.

• do you have a utility method that exposes your internal map that "shouldnt be used" or
• is your internal map identified as public scope

Answer 4

This exception does not normally have anything to do with synchronization - it is normally thrown if a a Collection is modified while an Iterator is iterating through it. AddAll methods may use an iterator - and its worth noting that the posh foreach loop iterates over instances of Iterator too.

e.g:

for(Object o : objects) {
    objects.remove(o);
}

is sufficient to get the exception on some collections (e.g ArrayList).

James

Answer 5

Is internalMap static? You may have multiple objects, each locking on this, the object, but not providing correct locking on your static internalMap.

Answer 6

If you constructed LinkedHashMap with accessOrder = true then LinkedHashMap.get() actually mutates the LinkedHashMap since it stores the most recently accessed entry at the front of the linked list of entries. Perhaps something is calling get() while the array list is making its copy with the Iterator.

Answer 7

I don't think your set()/get() are synchronized against the same monitor that rebuild() is. This makes it possible for someone to call set/get while the problematic line is being executed, specifically when iterating over they key set of the internalMap during the addAll() call (internal implementation that's exposed through your stack trace).

Instead of making set() synchronized, have you tried something along the lines of:

public void set(SomeKey key, SomeValue val) {
    synchronized(this) {
        internalMap.put(key, val); // or whatever your get looks like
    }
}

I don't think you need to synchronize get() at all, but if you insist:

public SomeValue get(SomeKey key) {
    synchronized(this) {
        internalMap.get(key); // or whatever your get looks like
    }
}

In fact, I think you're better off synchronizing against internalMap instead of this. It also doesn't hurt to make internalMap volatile, though I don't think this is really necessary if you're sure that set()/get()/rebuild() are the only methods directly accessing internalMap, and they are all accessing it in a synchronized manner.

private volatile Map internalMap ...

Answer 8

While iterating over the keys, due to

keysCopy.addAll(internalMap.keySet());

Do you decide that some of the entries can be removed from the LinkedHashMap?

The removeEldestEntry method could be either returning true, or modifying the map, thereby upsetting the iteration.

Answer 9

Try declaring the Map as transient

Answer 10

try this:

public void rebuild(){
  /* initialization stuff */
  List<SomeKey> keysCopy = new ArrayList<SomeKey>();
  synchronized (internalMap) {
    keysCopy.addAll(internalMap.keySet());
  }
  /* 
    do stuff with keysCopy, update a temporary map
   */    
  synchronized (internalMap) {
    internalMap.putAll(tempMap);
  }
}

Answer 11

From the Javadoc:

If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

It may be safer for you to actually wrap the LinkedHashMap rather than claim you extend it. So your implementation would have an internal data member which is the Map returned by Collections.synchronizedMap(new LinkedHashMap(...)).

Please see the Collections javadoc for details: Collections.synchronizedMap

Answer 12

Keep access to internalMap syncronized, otherwise java.util.ConcurrentModificationException occurs because HashMap#modCount (which records structural changes) can be changed concurrently during keyset iteration (due keysCopy.addAll(internalMap.keySet() invocation).

LinkedHashMap javaDoc specifies : "In access-ordered linked hash maps, merely querying the map with get is a structural modification."