Sunday, February 10, 2008

digsby: One Tool to rule them all

One Tool to rule them all, One Tool to find them,
One Tool to bring them all and in the darkness bind them

What am I speaking about? Oh, yes, it's digsby!

It combines several IM protocols, plus e-mail accounts, plus social network accounts in one single tool!

I was looking for a good IM client for quite some time now. I tried Miranda IM and Trillian, but they didn't prove satisfactory. Some days ago, I had the chance to get into the private beta of digsby, and till now, AFAICT, it looks quite compelling.

There's also a cool widget. You may have noticed it on my blog. Whenever I'm online, you're now able to directly chat with me over the embedded flash-application. Yes, unfortunately it's flash, but IMO this is one of the rare occasions where flash may be the right toolset. I know, you could do it with AJAX of course, but I like the fact that I don't have to deal with a mess of JavaScript (or ECMAScript, however you want to name it) but have an isolated*, embedded application running on my blog.

Unfortunately, digsby is still in private beta, but if you've some luck, ars technica may have some invitations left.

 

* hopefully the flash-app is running in an isolated context, I'm just assuming so

Tuesday, January 22, 2008

Newsqueak: A Language for Communicating with Mice

Did you know the programming language Newsqueak developed by Rob Pike? You should!

I was watching the Google Tech Talks video Advanced Topics in Programming Languages: Concurrency and Message Passing in Newsqueak where Rob Pike himself gives a short introduction into this programming language.

The following source code is an amazingly cool implementation of the Sieve of Eratosthenes (it just filters out all prime numbers):

1 counter:=prog(c:chan of int) 2 { 3 i:=2; 4 for(;;) 5 c<-=i++; 6 }; 7 filter:=prog(prime:int, listen,send:chan of int) 8 { 9 i:int; 10 for(;;) 11 if((i=<-listen)%prime) 12 send<-=i; 13 }; 14 sieve:=prog() of chan of int 15 { 16 c:=mk(chan of int); 17 begin counter(c); 18 prime:=mk(chan of int); 19 begin prog(){ 20 p:int; 21 newc:chan of int; 22 for(;;){ 23 prime<-=p=<-c; 24 newc=mk(); 25 begin filter(p, c, newc); 26 c=newc; 27 } 28 }(); 29 become prime; 30 }; 31 prime:=sieve();

If I aroused interest in you, you may want to read the original Article from Rob. There are more references here: http://plan9.bell-labs.com/who/rsc/thread/index.html.

Wednesday, October 17, 2007

Cool tools and cool games

Quite a long time without a post now and still no technical topic to blog about. I need to get some time free once to elaborate some interesting stuff. Currently I've to fill a gap in my knowledge and learn Java. As you know, C# was heavily inspired by this language so the differences shouldn't be that big. However, I came across many language/framework features that Java does better than C#/.NET, and vice versa (C# isn't a step backwards, quite the contrary but in some areas, the language/framework designers did a step backwards). It may be the topic of one of my next blogs. Today, I just want to mention some smaller stuff.

Furl

You may've noticed the new "Recent Links" section on the right side of my blog. It should show links to interesting web resources I've found. Of course not everything I'm reading will show up there, but the more interesting things will. I'm using furl to generate this list. That's really cool. When you come across something interesting, you just have to click "Furl It" on your installed furl-toolbar and the current url will be saved to your link-archive. Furl has many features like tagging the links. You can also share the links with the community on any website you want to (like I'm doing it on my blog). A very nice feature.

Portal

Today I played a very cool game. Maybe the best I've ever played: Portal. It's a "single-player first-person action/puzzle video game" --excerpt from Wikipedia. All you've got is a portal-gun (yes, a gun with wich you can make portals) to solve the puzzles. Just watch Valve's demonstration at youtube. It makes so much fun to play. The game's atmosphere is ingenious. A real "must play". The only drawback is that you've played through the game in about 2,5 hours and you just want Valve to publish more levels. Watch the demonstration!

Wednesday, September 19, 2007

Interception with Proxies

Do you know how .net Remoting works? It relys on a very cool feature of the .net framework: Interception.

What is Interception?

In short, you replace existing code with new code, at runtime. There are quite a lot of different solutions to replace code. The easiest solution is Inheritance. You can override virtual methods and replace its implementation with anything else. At runtime you can swap the instances as you want. The same works with Interface Dispatch*. The problem of this solution is, that you can only intercept virtual methods.

There may be the need to intercept all method calls. The best example is Remoting. You want to access an object as if it lives in the current application domain though it might be located at any other app domain which in turn may be located on another computer at the other side of the earth! Fortunately you can. The answer is Interception.

How does it work?

Everything you need is to create an instance from a RealProxy and obtain a __TransparentProxy from it. Now you can cast the __TransparentProxy to the actual type that you want to intercept and access it like the original object. Sounds easy. Of course, this approach is very easy to use and that makes it so cool. The CLR had made a big effort to have it working. Chris Brumme wirtes about it in his article about the __TransparentProxy.

You can intercept everything: Virtual methods, non-virtual methods and also field-access. Because properties and events are both a pair of two methods, you can intercept them too. The only things you can't intercept are static methods and static field-access. It wouldn't make sense anyway. Every field-access is translated to a call to System.Object's private FieldGetter and FieldSetter method. This methods use reflection to get or set a field and as you know, reflection is very slow in comparision to direct access. Though you shouldn't allow direct field access (always make fields private!), it doesn't matter.

How can we inject code?

There are two different ways to inject code. The easiest way is to use a ContextBoundObject and a ContextAttribute. There's an article at the msdn magazin about Contexts in .NET. This article desicribes very detailed how you can inject your custom code into a method call with this approach.

The second approach is to implement your own RealProxy. There is one short article about it at msdn: Extending RealProxy.

Here's a sample-implementation:

class InterceptionProxy : RealProxy
{
    MarshalByRefObject target;

    public InterceptionProxy(Type classToProxy, MarshalByRefObject target)
        : base(classToProxy)
    {
        this.target = target;
    }

    public override IMessage Invoke(IMessage msg)
    {
        IMethodCallMessage callMsg = msg as IMethodCallMessage;

        if (callMsg != null)
        {
            OnMethodCall(callMsg);
            IMethodReturnMessage retMsg = InvokeMethod(callMsg);
            OnMethodReturn(retMsg);
            return retMsg;
        }
        else
        {
            throw new NotSupportedException();
        }
    }

    IMethodReturnMessage InvokeMethod(IMethodCallMessage callMsg)
    {
        return RemotingServices.ExecuteMessage(target, callMsg);
    }

    void OnMethodCall(IMethodCallMessage callMsg)
    {
    }

    void OnMethodReturn(IMethodReturnMessage retMsg)
    {
    }
}
class Program : MarshalByRefObject
{
    void Test()
    {
        Console.WriteLine("Test");
    }

    static void Main(string[] args)
    {
        Program program = new Program();
        RealProxy proxy = new InterceptionProxy(typeof(Program), program);
        Program proxiedProgram = (Program)proxy.GetTransparentProxy();
        proxiedProgram.Test();
    }
}

If you debug the code, you can see that proxiedProgram is a __TransparentProxy instead of a Program. Every call to the __TransparentProxy is converted to a call of our InterceptionProxy's Invoke method. In this method we can do whatever we want. We just have to return a valid return message.

In our example we're only interested in method calls. We could also handle constructor calls (IConstructionCallMessage) by applying a ProxyAttribute on a ContextBoundObject:

class InterceptionProxy : RealProxy
{
    public InterceptionProxy(Type classToProxy)
        : base(classToProxy)
    {
    }

    public override IMessage Invoke(IMessage msg)
    {
        IConstructionCallMessage ctorMsg = msg as IConstructionCallMessage;

        if (ctorMsg != null)
        {
            return this.InitializeServerObject(ctorMsg);
        }
        else
        {
            throw new NotSupportedException();
        }
    }
}
class InterceptionProxyAttribute : ProxyAttribute
{
    public override MarshalByRefObject CreateInstance(Type serverType)
    {
        RealProxy proxy = new InterceptionProxy(serverType);
        return (MarshalByRefObject)proxy.GetTransparentProxy();
    }
}
[InterceptionProxy]
class Program : ContextBoundObject
{
    static void Main(string[] args)
    {
        Program program = new Program();
    }
}

When a new Program is created, first the InterceptionProxyAttribute's CreateInstance method is called. This method returns a __TransparentProxy instead of the Program. Notice that we have already a proxy before the constructor is called! Now the __TransparentProxy converts the call to the constructor to a call to our InterceptionProxy's Invoke method. To dispatch the contructor call, we use the RealProxy's InitializeServerObject method. You could get the created object by using the RealProxy's protected GetUnwrappedServer method.

Be aware that future method calls to the proxied instance aren't intercepted because the InitializeServerObject method told the __TransparentProxy that the proxied object is in the current context. It's actually the __TransparentProxy's stubData that holds this information. If it matches with the current context's InternalContextID, the __TransparentProxy invokes the called method directly instead of converting it to a call to the associated RealProxy's Invoke method. Fortunatly we can manipulated the stubData by the RealProxy's static GetStubData and SetStubData methods. If we set the stubData back to an IntPtr(-1), method calls are intercepted again.

Dispatching Messages

You saw two different ways to dispatch messages till now. Constructor calls were dispatched with the RealProxy's InitializeServerObject method and method calls were dispatched with the RemotingServices.ExecuteMessage method. These methods are quite slow because they add a lot of overhead. Actually all the arguments passed in by the message's Args property are checked if they match the called method's parameters. Therefor reflection is used which is very slow. This is really annoying because we are sure that the arguments must match the method's parameters. Otherwise the caller hadn't been able to call the method because already the compiler (C# compiler and JIT compiler) had issued an error. To circumvent the checks, we would need to call the internal System.Runtime.Remoting.Messaging.StackBuilderSink's PrivateProcessMessage method. This shouldn't be a problem if our assembly runs under full trust. With some hacks you can get even faster: Instead of using the IMethodCallMessage's MethodBase property (which is only created at the first access of the property) to obtain a RuntimeMethodHandle, you can use the Message's private _methodDesc field to create a new RuntimeMethodHandle from it. Be careful: This code depends on implementation details which are subject to change. The code can brake after you install a new patch for the framework!

Here's the code:

class InterceptionProxy : RealProxy
{
    delegate Object PrivateProcessMessage(
            RuntimeMethodHandle md, Object[] args, Object server, int methodPtr,
            bool fExecuteInContext, out Object[] outArgs);

    delegate RuntimeMethodHandle GetMethodHandle(IMethodCallMessage message);

    static GetMethodHandle getMethodHandle = CreateGetMethodHandle(); 

object target; PrivateProcessMessage privateProcessMessage; static GetMethodHandle CreateGetMethodHandle() { Type messageType = Type.GetType("System.Runtime.Remoting.Messaging.Message"); DynamicMethod dm = new DynamicMethod("", typeof(RuntimeMethodHandle),
new Type[] { typeof(IMethodCallMessage) }, typeof(InterceptionProxy), true); ILGenerator il = dm.GetILGenerator(); il.Emit(OpCodes.Ldarg_0); il.Emit(OpCodes.Castclass, messageType);
il.Emit(OpCodes.Ldfld, messageType.GetField("_methodDesc",
BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance));
il.Emit(OpCodes.Newobj, typeof(System.RuntimeMethodHandle).GetConstructor(
BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance,
null, new Type[] { typeof(IntPtr) }, null));
il.Emit(OpCodes.Ret); return (GetMethodHandle)dm.CreateDelegate(typeof(GetMethodHandle)); } public InterceptionProxy(Type classToProxy, object target) : base(classToProxy) { this.target = target; Type stackBuilderSinkType = Type.GetType(
"System.Runtime.Remoting.Messaging.StackBuilderSink");
object stackBuilderSink = Activator.CreateInstance(stackBuilderSinkType, target);
privateProcessMessage = (PrivateProcessMessage)Delegate.CreateDelegate(
typeof(PrivateProcessMessage), stackBuilderSink,
stackBuilderSinkType.GetMethod("PrivateProcessMessage",
BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance)); } IMethodReturnMessage InvokeMethod(IMethodCallMessage callMsg) { object ret; object[] outArgs; try { ret = privateProcessMessage(getMethodHandle(callMsg),
callMsg.Args, target, 0, false, out outArgs); } catch(Exception ex) { return new ReturnMessage(ex, callMsg); } return new ReturnMessage(ret, outArgs, outArgs == null ? 0 : outArgs.Length,
null, callMsg); } // other methods omitted }

If you don't need any details of the IMethodReturnMessage in the OnMethodReturn method, you can pass null instead of the callMsg to the constructor of the ReturnMessage to increase the performance even further. (The constructor would copy the MethodBase, along with other properties, from the callMsg to its own fields and so trigger the lazy creation of the MethodBase.)

Interception also works with interfaces and not only with childs of MarshalByRefObject. RemotingServices.ExecuteMessage required a MarshalByRefObject but our new approach doesn't require a special type.

I chose an even faster approach instead of using the StackBuilderSink's PrivateProcessMessage method. At the first call of a method, I create a DynamicMethod and cache it for future calls to the method. This approach is only faster if the same method is called a lot of times because the overhead of creating the DynamicMethod must pay off with the performance-win of the calls to the generated method.

The proxy would look like the following:

class InterceptionProxy : RealProxy
{
    delegate RuntimeMethodHandle GetMethodHandle(IMethodCallMessage message);

    delegate object DynamicMethodDelegate(object target, object[] args);

    static GetMethodHandle getMethodHandle = CreateGetMethodHandle();

    [ThreadStatic]
    static Dictionary<RuntimeMethodHandle, DynamicMethodDelegate> cache;

    object target;

    static GetMethodHandle CreateGetMethodHandle()
    {
        Type messageType = Type.GetType("System.Runtime.Remoting.Messaging.Message");
        
        DynamicMethod dm = new DynamicMethod("", typeof(RuntimeMethodHandle),
new Type[] { typeof(IMethodCallMessage) }, typeof(InterceptionProxy), true); ILGenerator il = dm.GetILGenerator(); il.Emit(OpCodes.Ldarg_0); il.Emit(OpCodes.Castclass, messageType); il.Emit(OpCodes.Ldfld, messageType.GetField("_methodDesc",
BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance)); il.Emit(OpCodes.Newobj, typeof(System.RuntimeMethodHandle).GetConstructor(
BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance,
null, new Type[] { typeof(IntPtr) }, null)); il.Emit(OpCodes.Ret); return (GetMethodHandle)dm.CreateDelegate(typeof(GetMethodHandle)); } static DynamicMethodDelegate CreateDynamicMethod(MethodInfo method) { ParameterInfo[] pi = method.GetParameters(); DynamicMethod dm = new DynamicMethod("", typeof(object),
new Type[] { typeof(object), typeof(object[]) },
typeof(InterceptionProxy), true); ILGenerator il = dm.GetILGenerator(); il.Emit(OpCodes.Ldarg_0); for (int i = 0; i < pi.Length; i++) { il.Emit(OpCodes.Ldarg_1); il.Emit(OpCodes.Ldc_I4, i); Type parameterType = pi[i].ParameterType; if (parameterType.IsByRef) { parameterType = parameterType.GetElementType(); if (parameterType.IsValueType) { il.Emit(OpCodes.Ldelem_Ref); il.Emit(OpCodes.Unbox, parameterType); } else { il.Emit(OpCodes.Ldelema, parameterType); } } else { il.Emit(OpCodes.Ldelem_Ref); if (parameterType.IsValueType) { il.Emit(OpCodes.Unbox, parameterType); il.Emit(OpCodes.Ldobj, parameterType); } } } if ((method.IsAbstract || method.IsVirtual)
&& !method.IsFinal && !method.DeclaringType.IsSealed) { il.Emit(OpCodes.Callvirt, method); } else { il.Emit(OpCodes.Call, method); } if (method.ReturnType == typeof(void)) { il.Emit(OpCodes.Ldnull); } else if (method.ReturnType.IsValueType) { il.Emit(OpCodes.Box, method.ReturnType); } il.Emit(OpCodes.Ret); return (DynamicMethodDelegate)dm.CreateDelegate(typeof(DynamicMethodDelegate)); } public InterceptionProxy(Type classToProxy, object target) : base(classToProxy) { this.target = target; } IMethodReturnMessage InvokeMethod(IMethodCallMessage callMsg) { DynamicMethodDelegate method; if (cache == null) { cache = new Dictionary<RuntimeMethodHandle, DynamicMethodDelegate>(); } if (!cache.TryGetValue(getMethodHandle(callMsg), out method)) { method = CreateDynamicMethod((MethodInfo)callMsg.MethodBase); cache.Add(callMsg.MethodBase.MethodHandle, method); } object ret; object[] args = callMsg.Args; try { ret = method(target, args); } catch(Exception ex) { return new ReturnMessage(ex, callMsg); } return new ReturnMessage(ret, args, args.Length, null, callMsg); } // other methods omitted }

I made the cache ThreadStatic to avoid the synchronization overhead for a shared dictionary.

There's one final word to say: Be careful with the logical call context! After our RealProxy's Invoke method returns, the current logical call context is set to the one specified in the return message. When we create the return message, we pass in null for the logical call context. This stores the current logical call context in the return message. When the current logical call context is changed between the creation of the return message and the return of the Invoke method (e.g. because of remote calls in the OnMethodReturn method), we will lose this changes.

Interception is a quite complex topic. Hopefully my research on Interception in the .net framework is useful for some of you. It took me quite a lot of time to figure all that stuff out. You may have a lot of questions to it. Just post a comment!


* Vance Morrison has written a cool article about how Interface Dispatch is implemented in the framework - it's quite complex.

Sunday, September 2, 2007

Windows Live Writer

What tool are you using for writing your blog posts? I was using the FCKEditor till now. The editor provided by blogger.com (where my blog is hosted) didn't fit my needs. It wasn't even a WYSIWYG editor and it was nearly impossible to get C#-code formatted with it. So I googled for a good HTML editor and soon came across the FCKEditor. It did quite a good job but it was a bit bulky to use. Whenever I wanted to post source code, I first copied the code from Visual Studio to Microsoft Word and from there to the FCKEditor. It worked, but everyone knows how good Microsoft Word is in exporting styles into HTML. I wasn't satisfied.

Two weeks ago, I happened to read a post listed by Jason Harley's Interesting Finds: August 24, 2007 about a the Windows Live Writer. After I read that it also supports blogger.com, I had to try it out. And I was amazed. It downloaded all the style informations from my blog and I was faced with a very cool and feature-rich WYSIWYG editor. There are plenty of plugins for the Windows Live Writer at the Windows Live Gallery. I instantly downloaded and installed the "Insert Fomatted Clipboard", "Paste from Visual Studio" and the "Code Snippet" plugin.

Now, this is my first post with this new, amazing tool and I really enjoy writing blog posts with it.

I'm very interested in other new tools from "Windows Live". Wikipedia lists quite a lot of products. It's time to take a closer look on them. Microsoft is really doing a great job in this area.

Saturday, August 18, 2007

Faster and more reliable ReaderWriterLock

Did you ever had the need of a very fast reader-writer lock? I had. I needed a cache (in the form of a generic Dictionary) which was accessed very very frequently. A normal lock would produce too much contention and the System.Threading.ReaderWriterLock has too much overhead. So I wrote my own reader-writer lock.

Here's the code:

public sealed class ReaderWriterLock
{
    int busy = 0;
    int numReads = 0;
 
    public void AcquireReaderLock()
    {
        Thread.BeginCriticalRegion();
 
        while (Interlocked.CompareExchange(ref busy, 1, 0) != 0)
        {
            Thread.Sleep(1);
        }
 
        Interlocked.Increment(ref numReads);
 
        Thread.VolatileWrite(ref busy, 0);
    }
    public void ReleaseReaderLock()
    {
        Interlocked.Decrement(ref numReads);
 
        Thread.EndCriticalRegion();
    }
    public void AcquireWriterLock()
    {
        Thread.BeginCriticalRegion();
 
        while (Interlocked.CompareExchange(ref busy, 1, 0) != 0)
        {
            Thread.Sleep(1);
        }
        while (Thread.VolatileRead(ref numReads) != 0)
        {
            Thread.Sleep(1);
        }
    }
    public void ReleaseWriterLock()
    {
        Thread.VolatileWrite(ref busy, 0);
 
        Thread.EndCriticalRegion();
    }
}

The busy flag is set as long as we're aquiring a reader lock (but not while we're reading) and during a whole write. This achieves that we can't take a reader lock while we are writing. Whenever we aquire a reader lock, a counter (numReads) is incremented. This counter tells us how many reads are currently in progress. When the reader lock is released, numReads is decremented again. At aquireing a writer lock, we've to wait till all reader locks have been released and so numReads reached 0 again.

Whenever we're waiting, we're calling Thread.Sleep(1). This gives other threads the chance to run and to release the lock again. We could do a better job here. Some calls to Thread.SpinWait before Thread.Sleep(1) would maybe do a better job on multi-processor machines. We could also move the thread in a waiting-queue if we can't aquire the lock after some interations. This would reduce CPU utilization on longer writes.

But there's another problem on which I'm focusing. Reliability. Did you notice the calls to Thread.BeginCriticalRegion and Thread.EndCriticalRegion? This tells the host of the CLR that we're using our own synchronization. Monitor.Enter and Monitor.Exit also call this two methods. Whenever something goes terribly wrong and so an asynchronous exception is thrown, this calls tell the host of the CLR that not only the current thread but the whole application domain is affected and has to be closed immediatly because it would be left in an incosistent state otherwise, what's even worse than an application crash because it leads to unpredictable behaviour or security vulnerability.

At the top I mentioned that I needed a cache which is used very very frequently. I'm building a logging-application. A cool feature of the .net Framework is interception with a pair of a __TransparentProxy and a RealProxy. It will be another post on how I'm using this interception technics for logging but you may read Chris Brumme's post. What you should know is, that I implemented my own RealProxy and overloaded the Invoke method which gets called whenever someone calls a method or accesses a field on the intercepted object. In this implementation, I've to call the actual method. One way would be to use reflection and call the MethodBase's Invoke method. This is quite slow. A faster way is to build up a DynamicMethod for every MethodBase (what's also damn fast) and call a delegate created from the DynamicMethod instead. That's what I'm doing. You can read more on DynamicMethods at Joel Pobar's article and blog post. To speed my code up even more, I'm caching the created delegates. Now imagine that some business-objects which are intercepted are called very very frequently. I tested this szenario and found two bottlenecks in my implementation of the RealProxy's Invoke method. The first one was the getter of the message's MethodBase property which retrieves the MethodBase from a CLR-internal cache by using the RuntimeMethodHandle as key. I invested no time to speed this up yet. The second bottleneck was the retrievement of the delegate from my dictionary. This was caused by the synchronization overhead of the lock. The most important code-path was the default case where I already had a delegate in the dictionary. I needed my own very fast synchronization code, the reader-write lock I posted.

As you can see, this reader-writer lock is used very frequently and from various threads. It isn't tolerable to have an app domain unload when one single thread is rudly aborted by a some code calling Thread.Abort. I already stated in the last post that you should never-ever use Thread.Abort, but I wanted my dictionary and that way also my reader-writer lock to support it. That's why I had to harden my code to accomplish a [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)].

Here's the hardened code:

public delegate void Code();

public sealed class ReliableReaderWriterLock
{
    int busy = 0;
    int numReads = 0;
    int version = 0;
 
    public void ExecuteWithReaderLock(Code code)
    {
        ReaderLockState state = new ReaderLockState();
        state.CurrentVersion = NewVersion();
 
        RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup(
            delegate
            {
                RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup(
                    delegate
                    {
                        while (Interlocked.CompareExchange(ref busy, state.CurrentVersion, 0) != 0)
                        {
                            Thread.Sleep(1);
                        }
                    },
                    ReaderLockIncrementReadsAndClearBusyFlag, state);
 
                code();
            },
            ReaderLockDecrementReads, state);
    }
 
    [PrePrepareMethod]
    void ReaderLockIncrementReadsAndClearBusyFlag(object userState, bool exceptionThrown)
    {
        ReaderLockState state = (ReaderLockState)userState;
 
        state.Reads = Interlocked.Increment(ref numReads);
        Interlocked.CompareExchange(ref busy, 0, state.CurrentVersion);
    }
 
    [PrePrepareMethod]
    void ReaderLockDecrementReads(object userState, bool exceptionThrown)
    {
        ReaderLockState state = (ReaderLockState)userState;
 
        if (state.Reads != 0)
        {
            Interlocked.Decrement(ref numReads);
        }
    }
 
    public void ExecuteWithWriterLock(Code code)
    {
        WriterLockState state = new WriterLockState();
        state.CurrentVersion = NewVersion();
 
        RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup(
            delegate
            {
                while (Interlocked.CompareExchange(ref busy, state.CurrentVersion, 0) != 0)
                {
                    Thread.Sleep(1);
                }
 
                while (Thread.VolatileRead(ref numReads) != 0)
                {
                    Thread.Sleep(1);
                }
 
                code();
            },
            WriterLockClearBusyFlag, state);
    }
 
    [PrePrepareMethod]
    void WriterLockClearBusyFlag(object userState, bool exceptionThrown)
    {
        WriterLockState state = (WriterLockState)userState;
 
        Interlocked.CompareExchange(ref busy, 0, state.CurrentVersion);
    }
 
    int NewVersion()
    {
        int currentVersion;
 
        // 0 is no valid version
        while ((currentVersion = Interlocked.Increment(ref version)) == 0)
            ;
 
        return currentVersion;
    }
 
    class ReaderLockState
    {
        public int Reads;
        public int CurrentVersion;
    }
    class WriterLockState
    {
        public int CurrentVersion;
    }
}

You can see quite a lot of changes. The most important change it the use of SRCSRHECWGC, pronounced “shreek shreck woogy-cuck”. Joe Duffy called the method System.Runtime.CompilerServices.RuntimeHelpers.ExecuteCodeWithGuaranteedCleanup so in his post about orphaned locks. This method ensures that the clean-up code (the second parameter of the method) is called, whatever happens. The clean-up code is called in a CER which means that a ThreadAbortException is delayed till the end of the CER and it's also guaranteed that the clean-up code has sufficient stack space to finish. You can read more about Constrained Execution Regions at this BCL Team Blog post. The ExecuteCodeWithGuaranteedCleanup method also ensures that the clean-up code is called in the case of a StackOverflowException in the try-code (the first parameter of the method). We don't just set the busy flag to 1 because we wouldn't be able to determine if we were successful. Therefor we use a version which is incremented on every lock. The busy flag is only cleared if it was set to the version we specified. So we can ensure that we don't set back the flag when another lock has set it and we were aborted by a ThreadAbortException before we could set the flag. Nearly the same is done with the count of concurrent reads (numReads). We store the result of the increment in the ReaderLockState.Reads field. If it was successfully changed from 0 to the new value, we know that we reached the increment call. The increment is done in a CER to ensure that there's no ThreadAbortException between the increment and the assignment to the ReaderLockState.Reads field. Otherwise we may leak a read and would never-ever be able to acquire a writer lock. There's one very very, very very very rare possibility of a malfunction. If there's one long-lasting read followed by so many reads that the version overflows and exactly the read which got the same version as the long-lasting read throws a ThreadAbortException just before the busy flag is set to the currentVersion, the failed read would clear the busy flag of the long-lasting read which may then experience a change on the synchronized objects. It's likelier that you win the lottery ten times in a row than that you run in this condition.

The reader-writer lock is hardened now. The last thing to do is to add the created delegate to the dictionary in a constrained manner. I don't want to have to throw away the whole dictionary if someone calls Thread.Abort in the middle of the dictionary's Add method. I'll have to write my own dictionary for this purpose. Fortunatily I have only two methods to implement: Add and TryGetValue, but both must accomplish a [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)].

Wow, that was quite a long post and hopefully you enjoyed it (I think you did if you read till here). If you find any bugs in the posted code or if you have any other annotations, be free to post a comment.

I haven't tried the new ReaderWriterLockSlim, which is shipped with the Orcas beta, yet. Also AFAIK it is not hardened. It'd be interesting if my code can match up with it.

Saturday, August 4, 2007

Do never-ever use Thread.Abort!

Here's why:

(I recommend reading Joe Duffy's blog first.)

We have this typical code:

lock (o)
{
    // do some stuff
}

This code is C#'s short syntax for the following:

Monitor.Enter(o);
try
{
    // do some stuff
}
finally
{
    Monitor.Exit(o);
} 

The try-finally block ensures that the lock will be released. Does it really ensure it? Two conditions have to be met!
1)      No exception must be thrown after the lock is acquired and before the try-block is entered. Because we have no code between Monitor.Enter and the start of the try-block, there can’t be an exception thrown.

2)      No exception must be thrown after the end of the try-block and before the lock is released. The CLR ensures that the finally block is executed regardless of any exception in the try-block. Because we have no code between the beginning of the finally-block and Monitor.Exit there can’t be an exception thrown either.

So everything looks fine, till we are using Thread.Abort to kill the thread.

How does Thread.Abort work?
Here’s the msdn-documentation of Thread.Abort:
“When this method is invoked on a thread, the system throws a ThreadAbortException in the thread to abort it. ThreadAbortException is a special exception that can be caught by application code, but is re-thrown at the end of the catch block […]”

“the system throws a ThreadAbortException in the thread” is formalized a little bit weakly. I would say “it injects a throw of a ThreadAbortException into the thread’s code”. Here’s the problem. If the exception is injected at a place where we don’t want to have it: BOOM! The thread will leave the rest of the process in an inconsistent state! You may ask why? I’ll show you three examples of where we do not want to have a ThreadAbortException:

1)      Between the Monitor.Enter and the beginning of the try-block:

Monitor.Enter(o);
throw new ThreadAbortException();
try
{
   
// do some stuff
}
finally
{
    Monitor.Exit(o);
}


As Joe Duffy states in his blog, this can’t occur (at least on x86-systems) because the instruction pointer (EIP) of an x86-based machine is pointing to the beginning of the try block after Monitor.Enter is executed. Assuming that Monitor.Enter is an atomic operation, the ThreadAbortException also can’t be thrown in the middle of Monitor.Enter.
The generated code would look like the following instead and because the CLR assures that the finally-block is called (also on a ThreadAbortException), we’ll have no problems.

Monitor.Enter(o);
try
{
    throw new ThreadAbortException();
   
// do some stuff
}
finally
{
    Monitor.Exit(o);
}

2)      Between the beginning of the finally-block and Monitor.Exit:

EDIT: A ThreadAbortException is always delayed till the end of a finally block. This is also the case for catch blocks and type initializers.

Monitor.Enter(o);
try
{
    // do some stuff
}
finally
{
    throw new ThreadAbortException();
    Monitor.Exit(o);
} 

The lock will not be released and whenever another thread tries to acquire a lock, it will be dead-locked because the lock will never be released by the aborted thread. Joe Duffy mentions another way to acquire the lock by using a Boolean variable:

bool taken;
try
{
    Monitor.RelaiableEnter(o, out taken);
    // do some stuff
}
finally
{
    if (taken)
    {
        Monitor.Exit(o);
    }
} 

This may eliminate the problem in example one but not in our second one.

And I promised a third example:

3)      While we are doing some stuff:

Why have we used a lock? Because we are doing some manipulations on shared state which is not atomic and so may leave the shared state inconsistent if we can’t finish the operations before another thread wants to access it. Take this simple code:

Monitor.Enter(o);
try
{
    object item = queue1.Dequeue();
    queue2.Enqueue(item);
}
finally
{
    Monitor.Exit(o);
} 

We move an item from one queue to another. That’s a common task: Take an item from one location and put it to another location. Now assume the thread is aborted and a ThreadAbortException is inject between the two lines:

Monitor.Enter(o);
try
{
    object item = queue1.Dequeue();
    throw new ThreadAbortException();
    queue2.Enqueue(item);
}
finally
{
    Monitor.Exit(o);
} 

The item will be lost! We’ve removed it from one queue but we weren’t able to put it into the other queue! One may argue that the item should only be removed from the first queue after we’ve put it into the second queue but this may result in having the item in both queues if the ThreadAbortException is raised between adding the item into the second queue and removing it from the first queue. At least we don’t have a deadlock in this case but the result isn’t better either!

What do I want to say with this? Do never-ever use Thread.Abort!

The only reasonable usage of Thread.Abort is at killing the process and that’s where Thread.Abort is used by the CLR. In my opinion, acquiring a lock should be paired with a call to Thread.BeginCriticalRegion and releasing a lock should be paired with Thread.EndCriticalRegion (EDIT: Monitor.Enter internally calls Thread.BeginCriticalRegion and Monitor.Exit calls Thread.EndCriticalRegion). Not only some hosts of the CLR but the CLR itself should react on an exception within a critical region by unloading the whole application domain because it’s not guaranteed to be stable anymore. (EDIT: According to cbrumme's WebLog, unhandled exceptions of threads which are not part of the ThreadPool and similar "reusable" threads - except ThreadAbortExceptions, which are always swallowed - lead to a termination of the whole process.)

A better solution would be to not having shared state but this would need a radical change of the whole threading-system (though I’ve some ideas on how a new threading-system may achieve this but that’ll be another post).

 

EDIT:
I had to do some edits on this post because I got to know that the CLR has some special, sparely documented behaviour. This leads to more stability of the CLR by eliminating the second problem. But it doesn't change the basic message because the first problem may still occur under certain circumstances (as described by Joe Duffy's blog post) and the third one is corrupting the data anyway. To draw a conclusion: The CLR is doing a better job than you may assume but there are still critical problems left when you're aborting a thread.