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.
