2007-11-14

Detecting Concurrent Changes with the Decorator Pattern

Recently, our bug tracking system started receiving reports of a ConcurrentModificationException. The API in question was only ever supposed to be used on one thread, and yet a caller somewhere was making modifications on a background thread.

One thing that makes it tricky to diagnose this kind of problem is that a ConcurrentModificationException thrown during iteration only tells you that a concurrent modification was detected. But no information is present in the stack trace about where the rogue write actually happened. Wouldn't it be nice to have something like this?

java.util.ConcurrentModificationException
  at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
  ...
Caused by: java.lang.Throwable: List modified
  at ...
  at org.foo.SomeRogueCaller.writeOnTheWrongThread(SomeRogueCaller.java:30)

It's pretty easy to do this using the decorator pattern. The basic idea is to write a decorator for java.util.List that records a stack trace when modifications are made to the list, and sets the trace of the last modification as the cause of any ConcurrentModificationException thrown while iterating.

I used the Google Collections Library as part of my implementation, primarily because its ForwardingList, ForwardingListIterator and ForwardingIterator base classes make it really easy to decorate the respective collections classes.

So the basic idea is to write a decorator that can audit writes. I created a subclass of ForwardingList that stores a Throwable representing the last modification. The audit method will be used to record modifications, and the setLastModificationAsCause method is used to initialize the cause of a ConcurrentModificationException to the last modification (if any).

final class AuditedWriteList<E> extends ForwardingList<E> {
  private Throwable lastModification;

  protected AuditedWriteList(List<E> delegate) {
    super(delegate);
  }

  private void audit() {
    synchronized (this) {
      lastModification = new Throwable( "List modified" );
    }
  }

  private void setLastModificationAsCause( Throwable t ) {
    synchronized (this) {
      if ( lastModification != null ) t.initCause( lastModification );
    }
  }

  // ...
}

Now, we override all List methods that modify the list, and make them audit. For example, here's the implementation for add(E):

@Override
public boolean add( E object ) {
  audit();
  return super.add( object );
}

Finally, we implement the iterator() and listIterator() methods to return a decorator Iterator and ListIterator respectively that catches a ConcurrentModificationException and calls the setLastModificationAndCause method:


@Override
public Iterator<E> iterator() {
  return new AuditingIterator<E>( super.iterator() );
}

// Inner class
private final class AuditingIterator<T> extends ForwardingIterator<T> {
  protected AuditingIterator(Iterator<T> delegate) {
    super( delegate );
  }
  
  @Override
  public T next() {
    try {
      return super.next(); 
    } catch ( ConcurrentModificationException e ) {
      setLastModificationAsCause(e);
      throw e;
    }
  }
}

Now, if we do something like this:

List<String> list = newAuditedWriteList( Lists.newArrayList( "One", "Two", "Three" ) );
for ( Iterator<String> i = list.iterator(); i.hasNext(); ) {
  i.next();
  list.add( "Four" );
}

We get a helpful stack trace telling us exactly where the modification took place. The beauty of the decorator approach is that the only change we made to our client code was to wrap the creation of our list with the call to newAuditedWriteList. Since this diagnostic is likely to be slow when there are a lot of writes, it could be conditionally turned on in debug environments.

The full source code is available in the dubh-examples google code module.

AddThis Social Bookmark Button

2 comments:

  1. Something I've experienced a few times is an assumption that ConcurrentModificationException automatically means you have a problem with threads.

    This article explains how you can experience the ConcurrentModificationException in a single thread:

    http://www.java2s.com/Tutorial/Java/0140__Collections/ConcurrentModificationException.htm

    ReplyDelete
  2. What a clever use of the ForwardingList! The authors' original intent was really to improve abstractions and eliminate repetition in the Collections library, it's nice to see it has other practical applications.

    You briefly mention enabling this only for debug environments. I haven't used Guice yet, and I know just a little bit about bytecode injection, but I keep thinking how one might use those to automatically provide this behavior to concrete list implementations, providing an easy way to track down such exceptions without recompiling code.

    Tangentially, here in Google Santa Monica, our Design Patterns reading group just finished discussing Decorator. Since people tend to think of patterns in their, shall we say, prototypical environment (GUI components, Java IO library), this helped reinforce the value of discussing patterns in non-standard environments.

    ReplyDelete