Dec 30, 2013 at 10:34 PM
Edited Dec 30, 2013 at 10:45 PM
I noticed a deadlock in my application that occurred in Update Controls. Since Update Controls tries to be thread safe, I thought I should mention it. The scenario is this: my program has a "combined search function" that performs fast and slow searches (the fast search scans in-memory data structures and gives immediate results, the slow search scans disk data structures and takes more time).

So I do the fast search on the UI thread and the slow search on a worker thread. A Dependent updated on the UI thread combines the results:
       A  B (Independents)    C   D (Independents)
       |  |                   |   |
       |  +-------------------+   |
       |  |                   |   |
       |  |                   +-+-+
       |  |                     |
       |  |                     v
       |  |                  Dependent
       |  |                     |  Dependent sends
       |  |                    ~~~ async message
       |  |                     |  to worker thread
       v  v                     |  (with copy of B C D)
     results1(Dependent)   results2(Independent)
       |                        |
       |                        |
A B C D represent the search parameters and search data (B and C are used by both searches while A and D are only used by one search type).

A deadlock happens as follows:

The UI thread updates A, B, C, or D (shouldn't matter which one).
  • results1.MakeOutOfDate() is called which locks results1.
  • results1.MakeDependentsOutOfDate() calls CombinedResults.MakeOutOfDate() which locks AllResults.
Meanwhile the worker thread changes results2.
  • AllResults.MakeOutOfDate() is called, which locks AllResults.
  • AllResults.MakeOutOfDate() calls results1.RemoveDependent(this), which locks results1 (DEADLOCK!)
Have you encountered this problem? Do you know of a general guideline for avoiding it?
Dec 30, 2013 at 10:58 PM
I have not run into this one before. I'll have to try to replicate it.

The strategy with locking in MakeOutOfDate has been to always lock in the precedent-to-dependent direction. Since this is a directed acyclic graph, that alone should not deadlock.

What I missed was that the locks to protect the list of dependents are executed in the dependent-to-precedent direction. You're walk through makes that clear.

I think the fix is to lock on a different object to protect the linked list of dependents. That way it won't be the same lock as the MakeOutOfDate chain going in the opposite direction. But I'll need to set up a test to make sure that that addresses the issue.

Jan 13, 2014 at 3:40 AM
After trying to replicate this deadlock, I realized that it should have been fixed about a year ago. Version should have included this fix (changeset 80240).

In the repro that you mention, MakeOutOfDate keeps results1 locked while it calls MakeDependentsOutOfDate. But after this change, it leaves the lock before making that call.

Are you perhaps using an older version?
Jan 13, 2014 at 4:31 AM
Oh yes, you're right, sorry, I have an old version. And I see the fix was easy, you just unlock results1 before locking AllResults.