The #develop teamblog
#  Saturday, January 26, 2008

In SharpDevelop 1.1, the IClass interface had a property that was used in several places in the code:
Once added to a project content, it was immutable. This was not enforced, not even documented. It just happened that no one changed IClass objects except for the code constructing them. After being added to a project content, a class could be removed or replaced by a new version, but if some code still held a reference to an old instance, it could safely access the members without worrying that an update to the class on another thread changed something.

IClass objects are accessed without locks all over the place on the main thread during code completion, and updates on the parser thread should not interfere with that.

However, because I didn't understand this, I broke it in SharpDevelop 2.0. My implementation of partial classes works as following: each file (compilation unit) contributes a part of the class as IClass object representing that part of the class.
Once multiple files register a part of the class in the project content, the project content creates a compound class. This compound class combines the members of all the parts. When updating a part, only the IClass for that part was recreated, and the existing CompoundClass was updated.

The CompoundClass, which could be in use by multiple threads, changed values. To quote Wes Dyer: "Mutation often seems to just cause problems."

Now, that happened to work correctly for quite some time. Most code iterating through a class' members did this with
foreach (IMethod method in c.Methods) {
}

where c is an IClass (possibly a CompoundClass). An update of the compound class happened to recreate the List<IMethod> behind the c.Methods property, so this code continued to work as expected.

However, in the quick class browser (the two combo boxes above the code window), there was code similar to this:
list.AddRange(c.Methods);
list.Sort();
list.AddRange(c.Properties);
list.Sort(c.Methods.Count, c.Properties.Count); // sort the properties without mixing them up with the methods

Suddenly, due to the addition of partial classes, this became a race condition waiting to happen. But it was found in time for the SharpDevelop 2.0 release, and I fixed the crash.
But I didn't know much about immutability back then, so what I did was the worst fix possible:
lock (c) { ... }
And in CompoundClass, during update of the parts: lock (this) { ... }

Now, this is not only bad because it's fixing the symptom instead of the problem and it leaves the possibility for similar problems elsewhere in the code - though it might have been the only instance of the problem, since no other crashes due to this have been found while SharpDevelop was using the fix (all 2.x releases use it, including the current stable release, SharpDevelop 2.2.1).

But multi-threading (without immutability) is not hard, it's really, really hard. So it's not really surprising that some day, I found this code to deadlock.

So where's the deadlock?
First I must tell you the other lock we're colliding with: every project content has a lock that it uses to ensure that GetClass() calls are not happening concurrently when the list of classes is updated. So the parser thread acquires the project content lock and then the CompoundClass lock to update the CompoundClass.

But why would the AddRange / Sort code deadlock with this? The comparer used for list.Sort() sorts the members alphabetically using their language-specific conversion to string. In the case of methods, this includes the parameter list, including the parameter types.

What you need to know here is that type references (IReturnType objects) are not immutable - they need to always reference the newest version of the class, as we cannot afford rebuilding all IReturnType objects from all classes in the solution whenever any class changes. Now remember that C# allows code like "using Alias = System.String; class Test { void Method(Alias parameter) {} }".

In this case, the quick class browser correctly resolves the alias and reports "Method(string parameter)". This means that our Sort() call actually sometimes needs to resolve types! And resolving types works using IProjectContent.SearchType, which locks on the project contents' class list lock. And that's our deadlock.

I think it's near impossible to find this kind of deadlock until it occurs and you can see the call stacks of the two blocked threads.
Remember that the actual Method->string conversion and the type resolving is language-specific; it may or may not happen to take a lock for other language binding AddIns.

I fixed the deadlock on trunk (SharpDevelop 3.0) a few months ago by removing the lock on CompoundClass and instead doing this:
list.AddRange(c.Methods);
list.Sort();
int count = list.Count;
list.AddRange(c.Properties);
list.Sort(count, list.Count - count);

It's still a hack, but this doesn't have any side effects (like taking a lock). And it works correctly under our (new) rule (undocumented rule, aka. assumption) that multiple c.get_Methods calls may return different collections, but the collection's contents don't change.

"foreach (IMethod method in c.Methods) { ... }" is safe, but "for (int i = 0; i < c.Methods.Count; i++) { IMethod method = c.Methods[i]; ... }" can crash.

But that's quite a difficult rule compared to "IClass never changes". So after reading Erip Lippert's series on immutability, I finally decided to make IClass immutable again.

It's "popsicle immutability", that means IClass instances are mutable, but when the Freeze() method is called, they become immutable. And this time, immutability is enforced, trying to change a property of a frozen IClass will cause an exception. Adding an IClass to a project content will cause it to freeze if it isn’t already frozen, so it's guaranteed that IClass objects returned by GetClass or by some type reference are immutable.

Categories: Daniel
Saturday, January 26, 2008 11:30:59 PM (GMT Standard Time, UTC+00:00)  #    Comments [0]

 



Comments are closed.

© Copyright 2014 SharpDevelop Core Team

Subscribe to this weblog's RSS feed with SharpReader, Radio Userland, NewsGator or any other aggregator listening on port 5335 by clicking this button.   RSS 2.0|Atom 1.0  Send mail to the author(s)

 

Copyright ©2000-2009 IC#Code. All rights reserved. Projects sponsored by AlphaSierraPapa.