Thread-safe enumeration in C#

Introduction

The IEnumerable interface in C# is a really useful abstraction. Introduction of LINQ in .NET 3.0 made it even more versatile. However, in a multithreaded environment, using it is wrought with peril, as the underlying collection may be modified anytime, instantly destroying your foreach loop or LINQ-expression.

I am going to suggest a simple trick that will make creating thread-safe enumerators super-easy, by strategically using another great interface: IDisposable.

Problems with iteration

As MSDN correctly states, "enumerating through a collection is intrinsically not a thread-safe procedure". Even if you use a synchronized collection (or one of the concurrent collections in .NET 4.0), and all methods use a lock statement internally, iteration using foreach may still fail. Another thread can change the collection when the control is inside the foreach loop - and thus, the collection is not locked - and bam, InvalidOperationException!

Traditionally, this problem is solved by wrapping the loop in a lock statement like this:

lock(collection.SyncRoot){
    foreach(var item in collection){
        // do stuff
    }
}

The problem with this approach is that the locking object is public, and anyone anywhere can lock on it. And, that is just inviting deadlocks.

Another way to have iteration in a thread-safe way is to simply make a copy of a collection:

foreach(var item in collection.Clone()){
    // do stuff
}

That assumes that the Clone() method is thread-safe. Even when it is, this pattern cannot boast high performance - we're actually iterating twice through the whole collection, to say nothing of allocating and then garbage-collecting memory for a clone.

Certainly, a much better way would be to write something like:

foreach(var item in collection.ThreadSafeEnumerator()){
    // do stuff
}

and have it be automatically thread-safe like in the first example. This is how to achieve this.

Creating a thread-safe enumerator

A great thing about foreach (and, by extension, LINQ) is that it correctly executes the Dispose() method of the enumerator. That is, foreach actually becomes a try-finally statement, where the enumerator is created, then iterated inside a try block, and disposed in finally. The IEnumerator<T> interface is actually inherited from IDisposable; its non-generic counterpart is not (because in .NET 1.0, foreach didn't work like that).

Taking advantage of this, we will create an enumerator that enters a lock in the constructor, and exits in Dispose(). This way, the collection will stay locked throughout the entire iteration, and no rogue thread will be able to change it.

public class SafeEnumerator<T>: IEnumerator<T>
{
    // this is the (thread-unsafe)
    // enumerator of the underlying collection
    private readonly IEnumerator<T> m_Inner;
    // this is the object we shall lock on. 
    private readonly object m_Lock;

    public SafeEnumerator(IEnumerator<T> inner, object @lock)
    {
        m_Inner = inner;
        m_Lock = @lock;
        // entering lock in constructor
        Monitor.Enter(m_Lock);
    }

    #region Implementation of IDisposable

    public void Dispose()
    {
        // .. and exiting lock on Dispose()
        // This will be called when foreach loop finishes
        Monitor.Exit(m_Lock);
    }

    #endregion

    #region Implementation of IEnumerator

    // we just delegate actual implementation
    // to the inner enumerator, that actually iterates
    // over some collection
    
    public bool MoveNext()
    {
        return m_Inner.MoveNext();
    }

    public void Reset()
    {
        m_Inner.Reset();
    }

    public T Current
    {
        get { return m_Inner.Current; }
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }

    #endregion
}

This is a trivial enumerator that enters lock on creation and exits on disposal. To actually use it, we must create a collection that uses it. For example:

public class MyList<T>: IList<T>{
    // the (thread-unsafe) collection that actually stores everything
    private List<T> m_Inner;
    // this is the object we shall lock on. 
    private readonly object m_Lock=new object();
    
    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        // instead of returning an usafe enumerator,
        // we wrap it into our thread-safe class
        return new SafeEnumerator<T>(m_Inner.GetEnumerator(), m_Lock);
    }
    
    // To be actually thread-safe, our collection
    // must be locked on all other operations
    // For example, this is how Add() method should look
    public void Add(T item)
    {
        lock(m_Lock)
            m_Inner.Add(item);
    }
    
    // ... the rest of IList<T> implementation goes here
}

This example shows a thread-safe wrapper around List<T>. This wrapper is absolutely synchronized - no other thread can do anything with it when it is used in a foreach loop.

Other neat stuff

Writing a thread-safe wrapper around List<T> (or any other collection) is useful; but we can make it even better. Let's make use of extension methods! First of all, here's a wrapper around IEnumerable<T>:

public class SafeEnumerable<T> : IEnumerable<T>
{
    private readonly IEnumerable<T> m_Inner;
    private readonly object m_Lock;

    public SafeEnumerable(IEnumerable<T> inner, object @lock)
    {
        m_Lock = @lock;
        m_Inner = inner;
    }

    #region Implementation of IEnumerable

    public IEnumerator<T> GetEnumerator()
    {
        return new SafeEnumerator<T>(m_Inner.GetEnumerator(), m_Lock);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion
}

Using this wrapper, we can write an extension for all enumerable collections:

public static class EnumerableExtension
{
    public static IEnumerable<T> AsLocked<T>(this IEnumerable<T> ie, object @lock)
    {
        return new SafeEnumerable<T>(ie, @lock);
    }
}

And now, we can lock any collection by simply using this method:

// in a class...
public class MyThreadSafeEnumerable<T>{
    // come collection of items..
    private IEnumerable<T> m_Items;
    private readonly object m_Lock=new object();
    // and thread-safe getter for them!
    public IEnumerable<T> Items{
        get
        {
            return m_Items.AsLocked(m_Lock);
        }
    }
}
    
// .. or simply in loop
foreach(var item in someList.AsLocked(someLock)){
    // ...
}

Neat, huh? Of course, that last example is in fact the same locking method from the beginning of the article. Still, it's arguably more readable. And, when the lock is made private, it's even more readable and less deadlock-prone.

Additional considerations

While it's all good when using foreach, using this enumerator by explicitly calling collection.GetEnumerator() is more dangerous than before. Forget to call Dispose() on it, and your collection is stuck in a lock forever. Implementing the finalization pattern on the enumerator might help with it, but really, the way to go is to never use GetEnumerator() unless absolutely necessary. And really, don't use it even then.

Also, it must be noted that even a private lock object doesn't guarantee deadlock-free code. As code inside a foreach loop may be arbitrary, one can still manage to deadlock. For example, like this:

// thread 1:
foreach(var item in SafeCollection){
    // do stuff
    lock(SomeObject){
        // do other stuff
    }
}

// thread 2:
lock(SomeObject){
    // do stuff
    SafeCollection.Add(foo); // <-Deadlock!
}

Here, the first thread locks the collection, then tries to enter the lock on SomeObject.. which is held by the second thread, and that waits on the collection's lock to add something to it. So, the lock is never released, and the threads hang up. Deadlocks are tricky like that. To remedy such a situation, you can add timeout to Monitor.Enter() in the constructor, and throw an exception if the timeout expired. Exception is still not a correct behaviour for a program, but it's arguably better than a deadlock - and certainly easier to debug!

Another possible upgrade to the thread-safe enumerator is using ReaderWriterLock (or even better, ReaderWriterLockSlim) in place of Monitor. As iterations do not change the collection, it makes sense to allow many concurrent iterations at once, and only block concurrent changes to the collection. This is what ReaderWriterLock is for!