Wednesday, November 23, 2011

ReaderWriterLock, C# Implementation With a Single Monitor

It turns out, it is not that hard to write a ReaderWriterLock in C# by using just a single monitor object:

public class ReaderWriterLock
{
public ReaderWriterLock()
{
m_activeReaderCount = 0;
m_activeWriter = false;

m_countLock = new object();
}

public void BeginRead()
{
Monitor.Enter(m_countLock);

while (m_activeWriter)
{
Monitor.Wait(m_countLock);
}

m_activeReaderCount++;

Monitor.Exit(m_countLock);
}

public void EndRead()
{
Monitor.Enter(m_countLock);

m_activeReaderCount--;
if (m_activeReaderCount == 0)
{
// At this point we are sure that only writers can be in the
// wait queue, so it is sufficient to wake up just one of them.
Monitor.Pulse(m_countLock);
}

Monitor.Exit(m_countLock);
}

public void BeginWrite()
{
Monitor.Enter(m_countLock);

while ((m_activeReaderCount != 0) || (m_activeWriter))
{
Monitor.Wait(m_countLock);
}

m_activeWriter = true;

Monitor.Exit(m_countLock);
}

public void EndWrite()
{
Monitor.Enter(m_countLock);

m_activeWriter = false;

// Both readers and writers can be in the wait queue.
// We will wake them up all and let them compete for
// the right to read / write.
Monitor.PulseAll(m_countLock);

Monitor.Exit(m_countLock);
}

private int m_activeReaderCount;
private bool m_activeWriter;
private object m_countLock;
}

Sunday, February 6, 2011

Experiment with CLR’s Assembly Loader: “LoadFrom Context and its Probing Logic”

Recently, while reading two well-known CLR-related books: Advanced .NET Debugging and CLR via C# I found an interesting discrepancy. More precisely, I was reading the chapters related to CLR’s Assembly Loader (Fusion). The exact subject was the probing logic that Fusion uses when loading an assembly via LoadFrom context.

The first book says that when we load an assembly by using LoadFrom context, loader doesn’t use any probing logic and just tries to load the assembly from the specified location. The second book states that loader will still try to load the assembly from GAC if the assembly with the same identity exists there.

So I decided to try it myself and see which of these two is correct.

First I wrote a very simple .cs file:

MyAssembly.cs

using System;
using System.Reflection;

[assembly: AssemblyTitle("MyAssembly")]
[assembly: AssemblyVersion("1.2.3.4")]

namespace MyAssembly.MyNamespace
{
    public static class MyClass
    {
        public static void MyMethod()
        {
            Console.WriteLine("MyMethod()");
        }
    }
}

And created an assembly called MyAssembly.dll with the following commands:

sn -k key.snk
csc /t:library /keyfile:key.snk MyAssembly.cs

Then, I wrote a simple program that loads the assembly by using LoadFrom context.

Program.cs:

using System;
using System.Reflection;

namespace Experiment
{
    public class Program
    {
        public static void Main()
        {
            Assembly.LoadFrom("MyAssembly.dll").GetType("MyAssembly.MyNamespace.MyClass").GetMethod("MyMethod").Invoke(null, null);

            Console.WriteLine("Press any key to quit.");
            Console.ReadKey(true);
        }
    }
}

Then I compiled the program with:

csc Program.cs

and installed MyAssembly.dll to GAC (the assembly was already in the same folder as the program).

gacutil /i MyAssembly.dll

Finally, I started the program under WinDbg and listed loaded modules:

> lmf

start             end                 module name
00000000`00ba0000 00000000`00ba8000   Program  C:\Experiment\Program.exe
00000000`75630000 00000000`75638000   MyAssembly
C:\windows\Microsoft.Net\assembly\GAC_MSIL\MyAssembly\v4.0_1.2.3.4__0e23280d1783e3a4\MyAssembly.dll
...

As you can see, the assembly was loaded from GAC, not from the private path C:\Experiment\MyAssembly.dll.

Now we can formulate the more accurate description of LoadFrom context’s probing logic. Assembly Loader first reads the identity of the assembly at given location and then tries to find the assembly with the same identity in the GAC. If that fails, assembly will be loaded from the given file.

My Favorite Software Development Books

During my short professional experience (something more than a year now) I’ve spent a lot of time reading about software development (mainly from Windows perspective). I’ve tried to choose practical books, because I wanted to apply that knowledge at work as soon as possible. Some of these books were recommended to me by more experienced colleagues, and I discovered others by chance.

Together they offer a broad coverage and can give you solid foundations of Windows software development. Some of them are fairly complex, so I had to read them 3-4 times to gain a better understanding. Back in the time I graduated, I didn’t quite realize what are the most useful books for someone about to start career in Windows software development. Therefore, I thought that these information might be of help to someone in similar situation.

So here it is, the list of my favorite (mainly Windows focused) software development books.

1. Advanced Windows Debugging

by Mario Hewardt, Daniel Pravat

Buy at Amazon.com

2. Advanced .NET Debugging

by Mario Hewardt

Buy at Amazon.com

3. CLR via C#, 3rd Edition

by Jeffrey Richter, Christophe Nasarre

Buy at Amazon.com

4. Windows via C/C++, 5th Edition

by Jeffrey Richter

Buy at Amazon.com

5. Windows System Programming, 4th Edition

by Johnson Hart

Buy at Amazon.com

6. Windows Internals, 5th Edition

by Mark Russinovich, David Solomon, Alex Ionescu

Buy at Amazon.com

7. Effective C++: 55 Specific Ways to Improve Your Programs and Designs, 3rd Edition

by Scott Meyers

Buy at Amazon.com

8. More Effective C++:  35 New Ways to Improve Your Programs and Designs

by Scott Meyers

Buy at Amazon.com

9. Design Patterns: Elements of Reusable Object-Oriented Software

by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides

Buy at Amazon.com

Wednesday, December 22, 2010

Iterative (Non-Recursive) Binary Tree Traversal Algorithms

Tree traversals are very frequent in everyday programming. Recursive implementations are trivial, but they are almost never used in practice. In this post I will implement four most important tree traversals: preorder, inorder, postorder and levelorder. To keep the things simple, I will use binary trees, with a very simple representation:

struct Node
{
    char value;
    Node* left;
    Node* right;
};

Also, I will visit individual nodes with the following following function:

void Visit(Node* node)
{
    cout << node->value;
}

I will use standard C++ and some STL containers. Traversal sequences will be tested on the following simple binary tree.

SimpleTree

As most other recursive algorithms, tree traversals can be easily implemented iteratively by using stack (levelorder is exception, since it is implemented by using the queue). Therefore additional space is used: O(n = number of nodes) in the worst case. Compared to recursion, this is still much better, because we push only necessary data on the stack (recursion additionally puts return address, registers,...). Additionally, stack overflow can't happen because STL containers use heap for storing their elements. Time complexity for all mentioned traversals is O(n).

Preorder Traversal

Expected Output: ABDGLEHICFJKM

Preorder is the simplest iterative tree traversal. We start by pushing the tree root to the stack. Then, until the stack is empty, we repeat the following routine: pop the next node and then push its children to the stack. First right then left, because we want the left sub-tree to be visited first.

void PreorderTraversal(Node* root)
{
    stack<Node*> s;

    if (root != NULL)
    {
        s.push(root);
    }

    while (!s.empty())
    {
        Node* current = s.top();
        s.pop();

        Visit(current);
       
        if (current->right != NULL) s.push(current->right);
        if (current->left != NULL) s.push(current->left);
    }
}

Inorder Traversal

Expected Output: LGDBHEIACJFKM

Inorder traversal is a bit trickier. We want the leftmost node to be visited first. Therefore, root node is pushed to the stack first, followed by its left child, then its leftmost grandchild,... until the leftmost node in the entire tree. Then we pop the nodes one by one. When we pop a node, we know that its left sub-tree has already been visited, so we visit the node itself. Then we push its right node, and similarly to what we have done with the root, we push its left child, then its leftmost grandchild,... until we push its leftmost descendant. Traversal then continues in similar fashion.

void InorderTraversal(Node* root)
{
    stack<Node*> s;

    Node* current = root;

    while (current != NULL)
    {
        s.push(current);
        current = current->left;
    }

    while (!s.empty())
    {
        current = s.top();
        s.pop();

        Visit(current);

        current = current->right;
        while (current != NULL)
        {
            s.push(current);
            current = current->left;
        }
    }
}

Postorder Traversal

Expected Output: LGDHIEBJMKFCA

Postorder is the most difficult tree traversal. It is similar to inorder traversal to some extent, but at the situations when inorder traversal pops and visits the node, postorder leaves the node on the stack and continues visiting its right sub-tree. When it finishes with the right sub-tree it pops the node from the stack and visits it. Obviously, each node is encountered two times, but it is the second time when we actually visit it. Therefore, some mechanism must be used to differentiate between these two situations. Some implementations put an additional flag to Node structure. In our case we don't want to change this structure, so we use an additional stack of bool values. For each element on the node stack, a corresponding value is stored on the bool stack. If this value is true, then we need to pop and visit the node on next encounter.

void PostorderTraversal(Node* root)
{
    stack<Node*> s;
    stack<bool> v;

    Node* current = root;

    while (current != NULL)
    {
        s.push(current);
        v.push(false);
        current = current->left;
    }

    while (!s.empty())
    {
        current = s.top();
       
        bool alreadyEncountered = v.top();
        if (alreadyEncountered)
        {
            Visit(current);
            s.pop();
            v.pop();
        }
        else
        {
            v.pop();
            v.push(true);

            current = current->right;
            while (current != NULL)
            {
                s.push(current);
                v.push(false);
                current = current->left;
            }
        }
    }
}

Levelorder Traversal

Expected Output: ABCDEFGHIJKLM

Levelorder traversal implementation is very similar to the preorder implementation, with the most significant difference that now the queue is used instead of stack.

void LevelorderTraversal(Node* root)
{
    queue<Node*> q;

    if (root != NULL)
    {
        q.push(root);
    }

    while (!q.empty())
    {
        Node* current = q.front();
        q.pop();

        Visit(current);

        if (current->left != NULL) q.push(current->left);
        if (current->right != NULL) q.push(current->right);
    }
}

Saturday, November 6, 2010

Common Resource Leak with Smart Pointers

One of the most common errors when dealing with smart pointers is creating a smart pointer object as a part of a function / method call.

For example:

DoSomething(shared_ptr<MyClass>(new MyClass), MyFunction());

Order in which function parameters are evaluated in C++ is not defined. (It is not from left to right like in C# and Java). Therefore, it is possible that a new MyClass object will be allocated first, and then MyFunction() called. In case when MyFunction() throws an exception, just created MyClass object will never be passed to a shared_ptr object. Therefore, it will never be be deallocated and this would result in a resource leak.

The following simple program demonstrates this error:

#include <memory>
#include <iostream>

using namespace std;
using namespace tr1;

class MyClass
{
public:
MyClass() { cout << "MyClass()" << endl; }
~MyClass() { cout << "~MyClass()" << endl; }
};

int MyFunction()
{
throw exception("New Exception!");
}

void DoSomething(shared_ptr<MyClass> myClass, int n)
{
// Add code here...
}

int main()
{
try
{
DoSomething(shared_ptr<MyClass>(new MyClass), MyFunction());
}
catch (exception e)
{
cout << "Exception caught: " << e.what() << endl;
}

return 0;
}

And in fact, most of the time I run this program, it results in a memory leak, which can be concluded from watching the output:

MyClass()
Exception caught: New Exception!

Obviously MyClass destructor wasn’t called.

To conclude the story, DoSomething() function call should be transformed to:

shared_ptr<MyClass> myClass(new MyClass);
DoSomething(myClass, MyFunction());

Now, if MyFunction() throws an exception, myClass object will be destroyed (since it is on the stack) and it will also deallocate MyClass object passed to it. We can take a look at the program output again and verify that the MyClass object has been destroyed.

MyClass()
~MyClass()
Exception caught: New Exception!

Sunday, October 10, 2010

ReaderWriterLock Implementation with Two Critical Sections

A few days ago I was reading a wiki article about reader-writer locks:


http://en.wikipedia.org/wiki/Readers-writer_lock


it references a Win32 implementation of this pattern at:


http://www.glennslayden.com/code/win32/reader-writer-lock


This implementation uses two critical sections and one auto-reset event.


I’ve realized that the same pattern can be implement without using auto-reset event (only with two critical sections). Here is the sample code:

class ReaderWriterLock
{
public:
ReaderWriterLock()
{
_readers = 0;
InitializeCriticalSection(&_rcs);
InitializeCriticalSection(&_wcs);
}

void BeginRead()
{
EnterCriticalSection(&_rcs);
if (_readers == 0)
{
EnterCriticalSection(&_wcs);
}
_readers++;
LeaveCriticalSection(&_rcs);
}

void EndRead()
{
EnterCriticalSection(&_rcs);
_readers--;
if (_readers == 0)
{
LeaveCriticalSection(&_wcs);
}
LeaveCriticalSection(&_rcs);
}

void BeginWrite()
{
EnterCriticalSection(&_wcs);
}

void EndWrite()
{
LeaveCriticalSection(&_wcs);
}

~ReaderWriterLock()
{
DeleteCriticalSection(&_rcs);
DeleteCriticalSection(&_wcs);
}

private:

int _readers;

CRITICAL_SECTION _rcs;
CRITICAL_SECTION _wcs;
};

Saturday, October 9, 2010

Cancelable Alternative to Thread.Sleep Method (C#)

Many times in the past I have seen fragments of code like this one:

private void MyThreadRun(object state)
{
    while (!m_myThreadCanceled)
    {
        // Do some processing here...

        Thread.Sleep(SleepInterval);
    } 
}

public void Cancel()
{
    m_myThreadCanceled = true;
}

private volatile bool m_myThreadCanceled;

What we have here is a thread doing some processing in regular intervals. The reason for not implementing this as a Task is that we have a lot of context (local variables) that we want to keep between iterations. Obviously, we don’t want this thread to run forever, so we want to have a way to cancel it (from another thread) in a safe way. This means that we don’t want to interrupt thread if it is currently in the processing phase (we don’t want to do a dangerous asynchronous thread abort operation). At the moment of cancelation, if the thread is in the processing phase, we want it to exit when it finishes with processing. On the other hand, if the thread is in its waiting phase we want it to exit immediately.

However, the code above doesn’t accomplish that. There is a great chance that we will try to cancel thread in the middle of Thread.Sleep(int) method, which means that thread will have to wait for a Thread.Sleep(int) method to finish before it exits. This is not what we want. Let’s say that we try to terminate our application gracefully (by canceling threads like the one above), that means that termination might take very long (up to SleepInterval)!

Here is a simple solution for this problem:

private void MyThreadRun()
{
    while (!m_lightSleeper.HasBeenCanceled)
    {
       // Do some processing here...

        m_lightSleeper.Sleep(SleepInterval);
    }
}

public void Cancel()
{
    m_lightSleeper.Cancel();
}

private LightSleeper m_lightSleeper = new LightSleeper();

Obviously, we rely on LightSleeper class. Cancel() method cancels the m_lightSleeper object. At the moment of cancelation, if the thread is in its processing phase, it will complete processing, m_lightSleep.Sleep(SleepInterval) will immediately return, while loop will complete and thread will exit. If the thread is in waiting phase, m_lightSleeper.Sleep(SleepInterval) will return immediately, and thread will exit in the same way as in the previous case. This is exactly the kind of behavior that we want.

Now lets describe LightSleeper class.

public class LightSleeper
{
    /// <summary>
    /// Sleeps for the specified amount of time.
    /// It can wake up earlier if Cancel() is called during the sleep.
    /// Also, it returns immediately if Cancel() has already been called.
    /// </summary>
    /// <param name="millisecondsTimeout">Sleep interval in milliseconds.</param>
    /// <returns>True if sleep wasn't canceled, false otherwise.</returns>
    public bool Sleep(int millisecondsTimeout)
    {
        return !m_manualResetEvent.WaitOne(millisecondsTimeout);
    }

    /// <summary>
    /// Cancels the current sleep operation (if there is one in progress),
    /// and causes all future sleep operations to return immediately when called.
    /// </summary>
    public void Cancel()
    {
        // Only one thread calling Cancel() can actually set the event.
        if (Interlocked.Exchange(ref m_canceled, Canceled) == NotCanceled)
        {
            m_manualResetEvent.Set();
        }
    }

    /// <summary>
    /// Returns true if light sleeper has been canceled.
    /// </summary>
    public bool HasBeenCanceled
    {
        get 
        {
            return (m_canceled == Canceled); 
        }
    }

    private const int NotCanceled = 0;
    private const int Canceled = 1;

    private int m_canceled = NotCanceled; 
    private ManualResetEvent m_manualResetEvent = new ManualResetEvent(false);
}

The roles of all methods are described by documentation comments, but let’s discuss this class in more detail. Sleep(int) method waits on a ManualResetEvent. Therefore if Cancel() – which sets this event – has already been called, WaitOne() method will return immediately. If Cancel() hasn’t been called, it will start sleeping, but will wake up if Cancel() is called during the sleep. In the last scenario Cancel() won’t be called during the Sleep(int) operation, and Sleep(int) will return after the given millisecondsTimeout expires. Sleep(int) method returns true if it wasn’t canceled, otherwise it returns false.

Cancel() method is used to wake up current thread from the sleep (by setting m_manualResetEvent) and to set HasBeenCanceled property to true. Case where several threads try to cancel current thread is valid, and therefore by using Interlocked.CompareExchange(ref int, int) method we make sure that only one thread can actually cancel the LightSleeper.

HasBeenCanceled property, as expected, returns true if LightSleeper has been canceled. It does so by reading m_canceled property. Here we want to return the freshest value of m_canceled variable. There is a possibility that the current value of m_canceled read from the current processor’s cache is not up to date. Normally, we would call Thread.VolatileRead(ref m_canceled) to achieve this, but in this case it is not necessary, since Interlocked.CompareExchange method made sure that the variable has been updated immediately in caches of all processors. Therefore, here we gain a bit on performance by not using the more expensive method.

Reason for m_canceled being int is that Interlocked.CompareExchange() method doesn’t accept bool as an argument.

Also, you might notice that LightSleeper doesn’t implement IDisposable interface. This class uses a ManualResetEvent which is disposable class, so it is recommended that it also implements disposable pattern. However, LightSleeper is used by at least two threads and can could cause ObjectDisposedExceptions if the “cancelable” thread completes before Cancel() was called by “canceling” thread. In this particular case lightSleeper object could be disposed when the “cancelable” thread completes, so “canceling” thread would try to call Cancel() on disposed object. We simplify the problem by not implementing IDisposable. Threfore, if Cancel() is called after “cancelable” thread completes it won’t have any effect.