Deadlock in Parallel.ForEach with ReaderWriterLockSlim

Question

I have an interesting problem with deadlocks in an my application. There is an in-memory data store that uses a ReaderWriterLockSlim to synchronize reads and writes. One of the read methods uses Parallel.ForEach to search the store given a set of filters. It's possible that one of the filters requires a constant-time read of same store. Here is the scenario that's producing a a deadlock:

UPDATE: Example code below. Steps updated with actual method calls
Given singleton instance store of ConcreteStoreThatExtendsGenericStore

1. Thread1 gets a read lock on the store - store.Search(someCriteria)
2. Thread2 attempts to update the store with a write lock - store.Update() -, blocks behind Thread1
3. Thread1 executes Parallel.ForEach against the store to run a set of filters
4. Thread3 (spawned by Thread1's Parallel.ForEach) attempts a constant-time read of the store. It tries to get a read lock but is blocked behind Thread2's write lock.
5. Thread1 cannot finish because it can't join Thread3. Thread2 can't finish because it's blocked behind Thread1.

Ideally what I'd like to do is not try to acquire a read lock if an ancestor thread of the current thread already has the same lock. Is there any way to do this? Or is there a another/better approach?

public abstract class GenericStore<TKey, TValue>
{
    private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim();
    private List<IFilter> _filters;  //contains instance of ExampleOffendingFilter

    protected Dictionary<TKey, TValue> Store { get; private set; }

    public void Update()
    {
        _lock.EnterWriterLock();
        //update the store
        _lock.ExitWriteLock();
    }

    public TValue GetByKey(TKey key)
    {
        TValue value;
        //TODO don't enter read lock if current thread 
        //was started by a thread holding this lock
        _lock.EnterReadLock();
        value = Store[key];
        _lock.ExitReadLock();
        return value;
    }

    public List<TValue> Search(Criteria criteria)
    {
        List<TValue> matches = new List<TValue>();
        //TODO don't enter read lock if current thread 
        //was started by a thread holding this lock
        _lock.EnterReadLock();
        Parallel.ForEach(Store.Values, item =>
        {
            bool isMatch = true;
            foreach(IFilter filter in _filters)
            {
                if (!filter.Check(criteria, item))
                {
                    isMatch = false;
                    break;
                }
            }
            if (isMatch)
            {
                lock(matches)
                {
                    matches.Add(item);
                }
            }
        });
        _lock.ExitReadLock();
        return matches;
    }
}

public class ExampleOffendingFilter : IFilter
{
    private ConcreteStoreThatExtendsGenericStore _sameStore;

    public bool Check(Criteria criteria, ConcreteValueType item)
    {
        _sameStore.GetByKey(item.SomeRelatedProperty);
        return trueOrFalse;
    }
}

Answer 1

It's unclear what kind of concurrency, memory and performance requirements you actually have so here are a few options.

If you are using .Net 4.0, you could replace your Dictionary with a ConcurrentDictionary and remove your ReaderWriterLockSlim. Keep in mind that doing that will reduce your locking scope and change your method semantics, allowing changes to the contents while you're enumerating (among other things), but on the other hand that will give you a threadsafe enumerator that won't block reads or writes. You'll have to determine if that's an acceptable change for your situation.

If you really do need to lock down the entire collection in this way, you might be able to support a recursive lock policy (new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion)) if you can keep all operations on the same thread. Is performing your search in parallel a necessity?

Alternately, you may want to just get a snapshot of your current collection of values (locking around that operation) and then perform your search against the snapshot. It won't be guaranteed to have the latest data and you'll have to spend a little time on conversion, but maybe that's an acceptable tradeoff for your situation.