9

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")?

12
  • OT, but arn't you in danger of missing any changes to the class in the commented region between the two synchronized methods in rebuild()?
    – DaveR
    Jul 6, 2009 at 22:51
  • Yes, you are absolutely correct; but according to the design docs, it's acceptable to have somewhat stale data :)
    – Cambium
    Jul 6, 2009 at 22:53
  • 2
    Damn, I wish I had design docs like that ;)
    – DaveR
    Jul 6, 2009 at 22:54
  • Sorry, but can you show the declaration and initialization of the internalMap?
    – Tom
    Jul 6, 2009 at 23:14
  • could you also show that ConcurrentModificationException stack
    – akf
    Jul 6, 2009 at 23:20

12 Answers 12

7

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.

3
  • Assuming no one calls get() while it's doing the copy, could this still trigger the exception? You raise a very good point though, I will look into the LinkedHashMap implementations. Thanks!
    – Cambium
    Jul 7, 2009 at 0:14
  • Based on your comment above that you use accessOrder, and assuming you have to call get() within the rebuild function (since all you show is grabbing keys), this seems a likely culprit. Do the rebuild() calls ever overlap? Jul 7, 2009 at 0:29
  • I imagine methods like containsKey() or containsValue() would also mutate the map, but the documentation for LinkedHashMap is silent on this issue. Jul 7, 2009 at 0:58
7

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

3
  • 1
    Hi James, I fail to see how this is relevant. I don't think I am modifying the map/keyset of the map while iterating through it.
    – Cambium
    Jul 6, 2009 at 23:42
  • @Cambrium - This is in fact the only way for this exception to occur - stackoverflow.com/questions/602636/…
    – Robin
    Jul 7, 2009 at 15:03
  • It is relevant because the exception is being thrown from your code almost certainly in the manner I describe.
    – gub
    Jul 7, 2009 at 23:13
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.

3
  • Yes, all of those methods are in the wrapper class.
    – Cambium
    Jul 6, 2009 at 23:17
  • Is there any code in your project that uses an iterator for this class? Are those uses synchronized properly?
    – Skip Head
    Jul 6, 2009 at 23:33
  • This class has no iterator. The internal map can only be modified via the three methods I listed above.
    – Cambium
    Jul 6, 2009 at 23:39
1

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

0

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.

2
  • Thanks for the suggestion, can you elaborate a little as to why that might solve the problem? I will give it a try shortly.
    – Cambium
    Jul 6, 2009 at 22:54
  • Given that the internal map can only be accessed via the wrapper changing the lock will make no difference. You will just be moving text around for no benefit.
    – mP.
    Jul 7, 2009 at 14:07
0

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
2
  • No, keySet() is not overriden. I don't think this will cause a problem though because the only way to access this internal map is through the wrapper class's set(), get() and rebuild().
    – Cambium
    Jul 6, 2009 at 23:21
  • I completely agree with your analysis, however, I triple/quadruple checked my class, and made sure that those three methods are the only accessors of the internal map; and of course, internal map is private.
    – Cambium
    Jul 6, 2009 at 23:50
0

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

0
0

Try declaring the Map as transient

1
  • damn, I meant to say volatile, as Jack mentions below
    – Reed
    Jul 7, 2009 at 1:12
0

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.

0

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 ...
0

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);
  }
}
0

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."

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.