A handler of a filter change that touches the source deadlocks with a writer of the source

Open
  • Is something wrong?
#145 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
csharp
Domain
backend

Research direction

Start with the repro in the issue, run with the join timeout to confirm the deadlock. The lock ordering lives in AttachFilter and ResetFilter of ObservableList<T>.View<TView>, which raise Reset inside lock (SyncRoot), and in SourceCollectionChanged, which takes the view lock inside the source lock. The same pattern appears in the other five view types. Done means the repro completes, or the no-touch rule is documented, and the choice is applied consistently. The fix depends on #125 and needs a maintainer decision first.

Written by the indexing model from the issue text.

Description

Summary

AttachFilter and ResetFilter of a view raise the Reset of the filter change while they hold the lock of the view only. A change of the source takes the lock of the source first, and then the lock of the view. When a handler of that Reset touches the source while another thread writes the source, the two threads take the two locks in opposite orders and deadlock.

Reading the source is enough, because ObservableList<T>.Count and its indexer take the lock of the source. Writing through a writable view list (notify[0] = ...) takes it as well.

Repro

using System.Collections.Specialized;
using ObservableCollections;

var list = new ObservableList<int>(new[] { 1, 2, 3 });

var sourceLockHeld = new ManualResetEventSlim();
// subscribed before the view, so it runs inside the lock of the source before the view handles the change
list.CollectionChanged += (in NotifyCollectionChangedEventArgs<int> e) => sourceLockHeld.Set();

var view = list.CreateView(x => x);
var notify = view.ToNotifyCollectionChanged();

notify.CollectionChanged += (_, e) =>
{
    if (e.Action != NotifyCollectionChangedAction.Reset) return;

    // another thread writes the source meanwhile
    new Thread(() => list.Add(4)) { IsBackground = true }.Start();
    sourceLockHeld.Wait();

    _ = list.Count;
};

var filter = new Thread(() => view.AttachFilter(x => x > 1)) { IsBackground = true };
filter.Start();

Console.WriteLine(filter.Join(TimeSpan.FromSeconds(3)) ? "completed" : "deadlocked");
// deadlocked

Replacing _ = list.Count with notify[0] = 10, on a list from list.CreateWritableView(x => x).ToWritableNotifyCollectionChanged(), deadlocks the same way.

Both were observed on master (a78ba19) and on the branch of #125 (7f9dc08). The ManualResetEventSlim only makes the timing deterministic; without it, the same deadlock happens whenever a writer of the source comes in while the handler runs.

Cause

AttachFilter raises the Reset inside the lock of the view (ObservableList<T>.View<TView>; ResetFilter is the same):

lock (SyncRoot)
{
    this.filter = filter;
    // ...
    ViewChanged?.Invoke(new SynchronizedViewChangedEventArgs<T, TView>(NotifyCollectionChangedAction.Reset, true));
}

The source raises a change inside its own lock, and the view takes its lock inside that:

// ObservableList<T>.Add
lock (SyncRoot)
{
    // ...
    CollectionChanged?.Invoke(NotifyCollectionChangedEventArgs<T>.Add(item, index));
}

// ObservableList<T>.View<TView>.SourceCollectionChanged
lock (SyncRoot)
{
    // ...
}

So the two threads take the locks in these orders:

  • the thread that changes the filter: the lock of the view, then the lock of the source (in the handler);
  • the thread that writes the source: the lock of the source, then the lock of the view.

The views of ObservableDictionary, ObservableHashSet, ObservableList, ObservableQueue, ObservableRingBuffer and ObservableStack all have the same AttachFilter and ResetFilter.

Suggested fix

Take the lock of the source before the lock of the view in AttachFilter and ResetFilter, so that every path takes the lock of the source first. The constructor of the view already takes the lock of the source. A writer of the source already waits for the lock of the view while a filter change runs, so the extra wait falls mainly on the readers of the source.

On master, this alone does not make every path take the lock of the source first. The writes of a writable view (SetToSourceCollection and the other *SourceCollection methods of ObservableList<T>.View<TView>) take the lock of the view before the lock of the source. #125 removes that lock from them.

If that is not wanted, document that a handler of the notification of a filter change must not touch the source.

Dominant language
C#
Stars
1k
Forks
73
Avg merge
4d 18h
Merged PRs (30d)
1

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from Cysharp/ObservableCollections

All issues in Cysharp/ObservableCollections

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.