Memory leaks even with WeakReferences

A crash report arrived at my desk the other day. The system crashed because it ran out of memory. And the major memory consumer was a WeakHashMap. Very interesting, since WeakHashMaps are usually used to allow to free memory when it's needed.

First some background. Imagine you've build a JSP page which generates a HTML page with a lot of URLs on it. You construct those URLs from different parameters. You use URLEncoder since you need valid URLs independent of the URL parameter contents you print. Once everything works fine, you realize that your URLs share may strings. So URLEncoder is called very often unnecessarily. You try to optimize the situation by creating a cache for URLEncoder:

class CachedUrlEncoder {
 static private Map<String, String> encodedMap = new HashMap<String,String>();

 public String encode(String str) {
  String encodedStr = encodedMap.get(str);
  if (encodedStr == null) {
   encodedStr = URLEncoder.encode(str);
   encodedMap.put(str, encodedStr);
  }
  return encodedStr;
 }
}

(The example is not thread save by purpose. We are not talking about concurrency, are we? ;) Also notice, that the one parameter encode method is now deprecated, because it uses system default encoding to encode the string.)

This cache would fill up the memory very quickly. It's never cleared after all. But there is also no special point in time when the cache should be cleared. The cached data never becomes outdated. Actually a cache should use a lot of memory if memory is not required by other subsystems, and free the memory if it becomes required. For this purpose the Java runtime has the SoftReference, WeakReference and the utility classes which use them. WeakHashMap f.e. is the perfect match for this scenario. A WeakHashMap references the values using normal hard references, and the keys using weak references. As soon as the key is not referenced any more (soft or hard) the whole entry will be freed. Here's the example rewritten to use WeakHashMap:

class CachedUrlEncoder {
 private static Map<String, String> encodedMap = new WeakHashMap<String,String>();

 public String encode(String str) {
  String encodedStr = encodedMap.get(str);
  if (encodedStr == null) {
   encodedStr = URLEncoder.encode(str);
   encodedMap.put(str, encodedStr);
  }
  return encodedStr;
 }
}

That was easy. Sadly you will notice at runtime that this code contains a memory leak. A not so obvious one. Let's analyse the situation.

As I mentioned already the map entries will be freed as soon as the key is not referenced by hard or soft references any more. In our case this should be immediately. After we've written the encoded string to the output stream of the JSP page, the string is not referenced any more. Still we're experiencing a memory leak. As so often the devil is in the details. The Sun implementation of URLEncoder.encode() tries to optimize by returning the reference to the string it received, if there is no encoding work to do. This is clever. It saves resources. But in this case this bit us really bad. If encode() returns the same reference the code will call Map.put() with the same reference as key and value. It'd look like:

encodedMap.put(str, str);

After that line the map has an entry with a weak reference to str and a hard reference to str. The entry itself prevents that it is garbage collected!

That's mean.

The fix is simple, once one knows the cause. We render the optimization of URLEncoder useless:

class CachedUrlEncoder {
 private static Map<String, String> encodedMap = new WeakHashMap<String,String>();

 public String encode(String str) {
  String encodedStr = encodedMap.get(str);
  if (encodedStr == null) {
   encodedStr = URLEncoder.encode(str);
   if (str == encodedStr) {
    encodedStr = new String(encodedStr);
   }
   encodedMap.put(str, encodedStr);
  }
  return encodedStr;
 }
}

Luckily the implementation of the string constructor is also smart. It does not copy the char data. A new string object is created and references the same char array as the old string. This is safe since strings are immutable. So the fix does create some overhead but not that much.

A Executor is not a Thread - or: correct ThreadPoolExecutor error handling

Java 1.5 introduced the Executor framework. In summery: if you have some tasks (let's say: 20) and you want them to be processed in parallel by a couple of threads (let's say: 6), then a Executor is the solution you want to look for. But there are some surprising caveats which may lead to problems. And they are hard to diagnose.

Introduction

Executor is a interface. The ExecutorService interface extends Executor. One of the standard implementations of ExecutorService is ThreadPoolExecutor. This one manages some threads in a pool and executes the tasks you give it. You do this in form of a list of Runnable instances. A typical Runnable implementation looks like this:

public class MyWorker implements Runnable {
    private final Object data;

    public MyWorker(final Object data) {
        this.data = data;
    }

    @Override
    public void run() {
        process();
    }

    private void process() {
        // process data
    }
}

You initialize a ThreadPoolExecutor like this:

int nThreads = 8;
Executor executor = new ThreadPoolExecutor(nThread, nThreads, 0, TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>());

And since this is so cumbersome, there is a helper class for that:

int nThreads = 8;
Executor executor = Executors.newFixedThreadPool(nThreads);

This is how to use a Executor wrapped in a method:

public void executeRunnables(final List<Runnable> runnables) {
    int nThreads = 8;
    Executor executor = Executors.newFixedThreadPool(nThreads);
    for (final Runnable command : runnables) {
        executor.execute(command);
    }
}

This method would return to the caller immediately after creating the executor. But usually you want to wait until all the tasks have been processed before returning to the caller. For this purpose ExecutorService defines the methods shutdown() and awaitTermination():

public void executeRunnables(final List<Runnable> runnables) throws InterruptedException {
    final int nThreads = 8;
    final ExecutorService executor = Executors.newFixedThreadPool(nThreads);

    for (final Runnable command : runnables) {
        executor.execute(command);
    }

    executor.shutdown();

    executor.awaitTermination(2, TimeUnit.SECONDS);
}

(notice the change of executor type from Executor to ExecutorService) shutdown() puts the executor in "finish your work" mode. In this mode the executor will not accept new tasks. awaitTermination() waits until all threads processed all tasks. The time out takes care that your program doesn't wait forever if something goes wrong.

Error handling

So what if something goes wrong? What if one of your tasks throws an exception? How do you handle that? How do you even know something gone wrong? One possible approach is to catch and collect all exception inside the Runnable implementation:

public class MyRunnable implements Runnable {
    private final Object            data;
    private final List<Exception>   exceptions;

    public MyRunnable(final Object data, final List<Throwable> exceptions) {
        this.data = data;
        this.exceptions = exceptions;
    }

    @Override
    public void run() {
        try {
            process();
        } catch (final Exception ex) {
            exceptions.add(ex);
        }
    }

    private void process() {
        // process data
    }
}

But this approach has two major drawbacks: First, it would also catch the InterruptedException which may be used to control the thread under normal conditions. And second, the responsibility of error handling is moved to each Runnable implementation. You are going to implement a lot of Runnables and it's easy to forget something. Executor error handling calls for a generic solution.

Java 1.5 adds a method to register exception handlers for exactly this purpose: Thread.setUncaughtExceptionHandler(). Exceptions which are not handled by the run() method of the Thread implementation, will be forwarded to this handler. Let's modify the above example to use a exception handler:

/**
 * Implementation of a UncaughtExceptionHandler, which stores all exceptions in a List.
 */
private static class ExceptionCollector implements UncaughtExceptionHandler {
    final List<Throwable> exceptions = Collections.synchronizedList(new LinkedList<Throwable>());

    @Override
    public void uncaughtException(final Thread t, final Throwable e) {
        exceptions.add(e);
    }
}

/**
 * A ThreadFactory, which registers a UncaughtExceptionHandler.
 */
private static class ThreadWithUncaughtExHandlerFactory implements ThreadFactory {
    private final UncaughtExceptionHandler    exHandler;

    public ThreadWithUncaughtExHandlerFactory(final UncaughtExceptionHandler exHandler) {
        this.exHandler = exHandler;
    }

    @Override
    public Thread newThread(final Runnable r) {
        final Thread t = new Thread(r);
        t.setUncaughtExceptionHandler(exHandler);
        return t;
    }
}

public void executeRunnables(final List<Runnable> runnables) throws InterruptedException {
    final int nThreads = 8;
    // UnhandledExceptionHandler which will collect Exceptions:
    final ExceptionCollector exHandler = new ExceptionCollector();
    // create a executor with a custom Thread factory:
    final ExecutorService executor = Executors.newFixedThreadPool(nThreads,
                                       new ThreadWithUncaughtExHandlerFactory(exHandler));

    for (final Runnable command : runnables) {
        executor.execute(command);
    }

    executor.shutdown();

    executor.awaitTermination(2, TimeUnit.SECONDS);

    if (exHandler.exceptions.size() > 0) {
        // rethrow first of the collected exceptions
        throw new RuntimeException(exHandler.exceptions.size() +
                    " exceptions occured. First exception:", exHandler.exceptions.get(0));
    }
}

Now this looks good! If a exception is not handled by the Runnable implementations the Thread will get it and the Thread will pass it on to the uncaught exception handler. The handler will store it in the list for later usage. executeRunnables() waits until all Threads are done with work and checks the exception list then. If there is a entry it will be wrapped in a RuntimeException and rethrown. Instead of just passing the first exception, it's also possible to append the whole exception list to the thrown exception. This way the caller will be notified.

Or won't it?

Well, this article would probably not exist if everything would be that simple like it looks. The truth is: it doesn't work. At least not always. Which makes it even worse. Sometimes it works and sometimes it doesn't.

Problem analysis

A Thread is capable of processing only one Runable in general. When the Thread.run() method exits the Thread dies. The ThreadPoolExecutor implements a trick to make a Thread process multiple Runnables: it uses a own Runnable implementation. The threads are being started with a Runnable implementation which fetches other Runanbles (your Runnables) from the ExecutorService and executes them: ThreadPoolExecutor -> Thread -> Worker -> YourRunnable. When a uncaught exception occurs in your Runnable implementation it ends up in the finally block of Worker.run(). In this finally block the Worker class tells the ThreadPoolExecutor that it "finished" the work. The exception not yet arrived at the Thread class but ThreadPoolExecutor already registered the worker as idle.

And here's where the fun begins. The awaitTermination() method will be invoked when all Runnables have been passed to the Executor. This happens very quickly so that probably not any of the Runnables finished their work. A Worker will switch to "idle" if a exception occurs, before the Exception reaches the Thread class. If the situation is similar for the other threads (or if they finished their work), all Workers signal "idle" and awaitTermination() returns. The main thread reaches the code line where it checks the size of the collected exception list. And this may happen before any (or some) of the Threads had the chance to call the UncaughtExceptionHandler. It depends on the order of execution if or how many exceptions will be added to the list of uncaught exceptions, before the main thread reads it.

A very unexpected behaviour. But I won't leave you without a working solution. So let's make it work.

Correct solution

We are lucky that the ThreadPoolExecutor class was designed for extendibility. There is a empty protected method afterExecute(Runnable r, Throwable t). This will be invoked directly after the run() method of our Runnable before the worker signals that it finished the work. The correct solution is to extend the ThreadPoolExecutor to handle uncaught exceptions:

public class ExceptionAwareThreadPoolExecutor extends ThreadPoolExecutor {
    private final List<Throwable> uncaughtExceptions = 
                    Collections.synchronizedList(new LinkedList<Throwable>());

    @Override
    protected void afterExecute(final Runnable r, final Throwable t) {
        if (t != null) uncaughtExceptions.add(t);
    }

    public List<Throwable> getUncaughtExceptions() {
        return Collections.unmodifiableList(uncaughtExceptions);
    }
}

Resolving circular dependencies in c++

I stumbled several times already upon situations where I created a circular dependency between two classes. Probably like every c++ developer. A circular dependency is bad design in general, it increases coupling between classes and thus makes changes more difficult (Circular dependency - Wikipedia). But in some languages (for example Java) it's possible to create classes which depend on each other without compiler errors. So very often circular dependencies are created and used without noticing. Differently for C++. The strict processing order of C++ compilers will spill out a bunch of errors when you try to make two classes depend on each other.
But you surely had a reason for this attempt. So how you achieve your aim whilst avoiding a circular dependency? See this example of a thread safe, usage based, load balanced object pool implementation:

// File: ObjectPool.h

#pragma once

#include <list>
#include <stdlib.h>
using namespace std;

// provides basic locking capabilities
#include "Lock.h"

// object type supplied by the pool
#include "Element.h"

class ObjectPool {
private:
 list<Element*> elements_;
 Lock lock_;

public:
 ObjectPool(size_t size) {
  for (size_t i = 0; i < size; i++) {
   elements_.push_back(new Element());
  }
 }

 Element *take() {
  // acquires the pool lock. AutoLockAndRelease will release the lock when scope is left
  AutoLockAndRelease autoLock(lock_);

  Element *chosen = getLeastUsedElement();
  chosen->incUsageCount();
  return chosen;
 }

 void release(Element *element) {
  AutoLockAndRelease autoLock(lock_);

  assertThisIsOurElement(element);
  element->decUsageCount();
 }

private:
 // checks if this element belongs to this pool
 void assertThisIsOurElement(Element *element) {
  // implementation details omitted
 }

 Element *getLeastUsedElement() {
  // implementation details omitted
 }
};




// File: Element.h

#pragma once

class Element {
private:
 int usageCount_;

public:
 Element():usageCount_(0) {
 }

 void incUsageCount() {
  usageCount_++;
 }

 void decUsageCount() {
  usageCount_++;
 }

 int getUsageCount() {
  return usageCount_;
 }
};

This is how it'd be used:

ObjectPool pool(5);
Element *element = pool.take();
// use element
pool.release(element);

I spare you the implementation details of Lock.h. Just assume it contains a lock implementation capable of synchronizing threads.

I'd like to modify this object pool and add the capability to the element to release itself. Id' like to use the pool like this:

ObjectPool pool(5);
Element *element = pool.take();
// use element
element.release();

Here are the code changes implementing this feature:

// File: ObjectPool.h

 ...
public:
 ObjectPool(size_t size) {
  for (size_t i = 0; i < size; i++) {
   elements_.push_back(new Element(*this));
  }
 }

 ...




// File: Element.h
...
class Element {
private:
 int usageCount_;
 ObjectPool &parent_;

public:
 Element(ObjectPool &parent):usageCount_(0), parent_(parent) {
 }

 ...

 void release() {
  parent_.release(this);
 }
};

This example suffers from two problems:

1. A a very subtle problem: The reference to the ObjectPool instance is made public to the Entry instance before the constructor of the ObjectPool class finished initializing the instance. This is known as early reference leak and should be avoided (Java theory and practice: Safe construction techniques, Should you use the this pointer in the constructor?).
2. The obvious one: The example doesn't compile. My compiler issues the error "'ObjectPool' does not name a type". This arises from the attempt to create a circular dependency: ObjectPool depends on Element, and Element depends on ObjectPool.

Let's first have a look at what we actually are trying to achieve here. The ObjectPool class manages a specified amount of entries. For each entry a usage count is maintained. The user can call take() to receive the entry with the lowest usage count. The ObjectPool class will use a lock to synchronize take() and release() invocations so it can be used safely in a threaded context. Once the user is done using a entry he invokes release() on the entry which then invokes release() on its parent which does a synchronized release. So how do we resolve the circular dependency while preserving the logic?

The solution is to decouple the ObjectPool and the Element class. I'll show here how to decouple both using a interface. The idea is, the Element class doesn't has to know the whole implementation of the ObjectPool class. It only needs to know the release() method. So we create a interface containing the release method and let ObjectPool implement the interface. Then we tell Entry only about the interface but not the ObjectPool class.

Here is the interface:

// File: Releaser.h

#pragma once

template<typename T>
class Releaser {
public:
 virtual ~Releaser() {};
 virtual void release(T *element) = 0;
};

It defines a single release method with a template type. The template type is essential here. Without the use of a template the interface would need to include Element type to use it as parameter type. But this would again create a circular dependency: ObjectPool -> Releaser -> Element -> Releaser. Using the template trick we break the cycle. Here are the modified implementations of ObjectPool and Element.

// File: ObjectPool.h

#pragma once

#include 
#include 
using namespace std;

#include "Lock.h"
#include "Element.h"
#include "Releaser.h"

class ObjectPool: public Releaser {
private:
 list elements_;
 Lock lock_;

public:
 ObjectPool(size_t size) {
  for (size_t i = 0; i < size; i++) {
   elements_.push_back(new Element(*this));
  }
 }

 Element *take() {
  AutoLockAndRelease autoLock(lock_);

  Element *chosen = getLeastUsedElement();
  chosen->incUsageCount();
  return chosen;
 }

 void release(Element *element) {
  AutoLockAndRelease autoLock(lock_);

  assertThisIsOurElement(element);
  element->decUsageCount();
 }

private:
 void assertThisIsOurElement(Element *element) {
  // implementation details omitted
 }

 Element *getLeastUsedElement() {
  // implementation details omitted
 }
};



// File: Element.h

#pragma once

#include "Releaser.h"

class Element {
private:
 int usageCount_;
 Releaser &releaser_;

public:
 Element(Releaser &releaser):usageCount_(0), releaser_(releaser) {
 }

 void incUsageCount() {
  usageCount_++;
 }

 void decUsageCount() {
  usageCount_++;
 }

 int getUsageCount() {
  return usageCount_;
 }

 void release() {
  releaser_.release(this);
 }
};

Now Element only references Releaser and the dependency cycle is broken.