Tip: Locking when calling external code
Can you spot the danger in the following code?
public T GetItem(Func<T, bool> finder)
{
T result = default(T);
lock (_itemsLock)
{
foreach (T item in _items)
{
if (finder(item))
{
result = item;
break;
}
}
}
return result;
}
How about in this?
public void HandleAdd(IEnumerable<T> addedItems)
{
lock (_itemsLock)
{
foreach (T item in addedItems)
{
_items.Add(item);
}
}
}
Don’t see it? Consider the following:
- Thread A, a background thread, is synchronizing changes made in-memory with the database:
- It already holds a lock on a class called "ChangeQueue".
- It calls HandleAdd(), passing in a list of changes.
- Thread B, the UI thread, is searching for something:
- It calls GetItem(), which acquires the lock for _itemLock.
- The delegate it passed to GetItem() accesses the ChangeQueue
See the problem now?
This is a deadlock scenario - thread A holds one lock and wants another, while thread B holds the second lock but wants the first. Neither can continue, the window stops processing messages, and Windows kindly renames your application to "(Not Responding)" and gives it a pretty shade of white :)
To lock A, or to lock B: that is the question
The common advice for these scenarios is that you should always acquire locks in the same order. Indeed, that’s easy to do within the same class, for example:
http://blog.w-nz.com/archives/2006/12/25/avoiding-multiple-lock-dead-locks-by-memory-addresses/
In this scenario above, however, I only wrote code for one of the locks. As the author of that code, I don’t even know about the other class or that it takes locks. What can I do to avoid deadlocks?
I learnt this the hard way with SyncLINQ. The code-base was littered with code like the above, until a couple of the unit tests I wrote to test threading started to fail just once every now and then. It took a while, but I eventually tracked it down to this pattern, and created my rule:
Never invoke code you don’t control whilst holding a lock.
The danger is that any code supplied externally could try to gain a lock themselves, and if you already hold one, you run the risk of deadlock. Delegates passed to methods, objects implementing an interface, or even calling virtual methods on classes you wrote yourself, can spell danger. For example, the IEnumerable<T> passed into the HandleAdd() method could try to acquire a lock in the GetEnumerator() method.
Avoidance
To avoid this problem, there are three tricks I normally use:
- Avoid locking where possible
- Take snapshots of the arguments, or invoke the methods before locking
- Build snapshots of my internals while holding a lock, then invoke outside methods after
For example, the two methods above could be re-written as follows:
public T GetItem(Func<T, bool> finder)
{
T result = default(T);
List<T> items = new List<T>();
lock (_itemsLock)
{
items.AddRange(items);
}
foreach (T item in items)
{
if (finder(item))
{
result = item;
break;
}
}
return result;
}
public void HandleAdd(IEnumerable<T> addedItems)
{
List<T> items = new List<T>();
items.AddRange(addedItems);
lock (_itemsLock)
{
foreach (T item in items)
{
_items.Add(item);
}
}
}
While not as efficient as the first, by executing the external code outside of the locks, I’ve avoided any accidental deadlock caused by interaction between my code and external code. You might consider caching the snapshots for next time - then you only pay when they have changed, versus every time you iterate.
Out of interest, I couldn’t find an FxCop rule for this. Anyone interested in writing one? 
Filed under: C#
I’m too distracted to fully evaluate your code. You’re new GetItem has a bug. I believe it’s just a typo, and the AddRange should have used _items in the call.
The HandleAdd I’m less certain about. I’m not sure what problem is trying to be solved here. It took me all of 3 seconds to recognize the problem with the GetItem, but here things are so obvious. Care to explain it a little deeper?
Have you read “Use Lock Hierarchies to Avoid Deadlock” (http://www.ddj.com/hpc-high-performance-computing/204801163 ) ? At least it provides an idea of how code from various sources can coordinate their locks.
Your experience might indicate that “green threads†(http://en.wikipedia.org/wiki/Green_threads) are better for making UIs responsive. Green threads like they are implemented in Smalltalk, will yield the same result for every execution of a unit test. Native threads might randomly fail like you describe.
For tasks that need to utilize multiple cores, C# and Java’s thread model will hopefully be replaced by better mechanisms (like shown in Erlang) some day.
@wekempf,
Since you don’t control the implementation of the IEnumerable passed to the HandleAdd method, you have no guarantee that it doesn’t try to take locks in the GetEnumerator. So, iterating over it whilst holding your own lock is a bad idea. Does that make sense?
I’d settle for an FxCop rule which simply looked for the “lock” keyword and threw this message:
“Locking is hard! Let’s go shopping!”
@Runar,
I had read about those rules, but again there’s no way to enforce the calling code follows them (imagine you’re a third-party control library vendor - you have no idea how people will use your controls). I’m familiar with green threads in ruby but I’m not convinced they’re a great approach - certainly they can be more predictable.
@Matt,
LOL!
A simple rule I follow is ‘you should only synchronise access to state not operations’ - so no locking on method calls only locking on local variables…
@Ollie
Agree, only ever lock on objects which are private…
[…] Locking Rule #71 - Paul Stovell takes a look at locking strategies. […]
May I suggest one small change to your rule? You write “Never invoke code you don’t control whilst holding a lock.” But the danger is only if the code you don’t control gets the SAME lock. So as long as it’s a lock *only your code knows about* you’ll be just fine. My revised wording:
“Never invoke code you don’t control whilst holding a lock you don’t own.”
(This implies a sense of “ownership” of locks… but I generally find I have just such a concept when I’m working.)
Hi Michael,
Not quite. Re-examine the scenario. MY code locks on MY locks, and they are private. The calling code locks on its own locks, and they are also private.
But since my code invokes theirs, and I take my own lock, my call into their code (invoking the delegate, for example) can cause them to take their lock. If this happens the other way around at the same time (i.e., they hold their lock on another thread, and call into my method in which I attempt to get my lock) then the deadlock occurs.
Trust me: I am not locking on public objects. I lock on private, read-only member fields of type object. I never share these objects outside the class. The calling code follows the same conventions. The deadlock scenario can still occur.
@Ollie, @Jordan - same response as above. In the example, lock(_itemsLock); _itemsLock is a private readonly field accessible only by the owning class. Deadlocks still happen.