InterlockedOr/And/ExchangeAdd in .NET

It’s reasonable to assume that the functions we need are hiding in the kernel32.dll module, just like the other Interlocked* functions. Being civilized people, we won’t go poking through this file with Far/Total Commander (although we do that plenty too :)) — instead we’ll examine it with Dependency Walker from the Visual Studio toolkit (Common7\Tools\Bin\Depends.Exe).

The result looks roughly like this:

The view might look a bit different on other systems, but on my Windows 2008 RC 2 only the basic Interlocked functions show up in this list. I’ll jump ahead and mention that on the x64 platform, kernel32.dll doesn’t have them at all. And if we look inside kernel32.lib from the Microsoft Platform SDK (this time with a plain text or binary editor), we’ll see that InterlockedOr isn’t there either.

The answer can be found in WinBase.h:

#if !defined (InterlockedOr)

#define InterlockedOr InterlockedOr_Inline

LONG
FORCEINLINE
InterlockedOr_Inline (
    __inout LONG volatile *Target,
    __in    LONG Set
    )
{
    LONG i;
    LONG j;

    j = *Target;
    do {
        i = j;
        j = InterlockedCompareExchange(Target,
                                       i | Set,
                                       i);

    } while (i != j);

    return j;
}

#endif

As you can see, the bitwise atomic operations are implemented as a loop around InterlockedCompareExchange, and nothing stops us from doing the same thing in C#. Here’s an example implementation of InterlockedOr that keeps the original syntax:

public static int InterlockedOr(ref int Target, int Set)
{
    int i;
    int j = Target;
    do
    {
        i = j;
        j = Interlocked.CompareExchange(ref Target, i | Set, i);
    }
    while (i != j);

    return j;
}

InterlockedAnd is implemented exactly the same way, just replacing i | Set with i & Set. I won’t explain how this code actually works here — I’ll point curious readers to primary sources, textbooks, or a bit of zen searching (http://dzen.yandex.ru/).

Now let’s get back to the exotic InterlockedExchangeAdd function. This function adds the given value to a variable and returns its old value. The difference from InterlockedAdd is minimal, and if you look at the .NET Framework through a decompiler, you’ll see that Interlocked.Add itself is implemented on top of ExchangeAdd, by adding the addend back in:

public static int Add(ref int location1, int value)
{
    return (ExchangeAdd(ref location1, value) + value);
}

This also holds in reverse: we can subtract the addend from the result of Interlocked.Add and get the same result as calling InterlockedExchangeAdd. This approach is universal, and for everyday use I recommend it specifically (for example, when porting code from C++ while keeping the original syntax and method names).
That would be a good place to end the article, but while preparing material for the second part of the “Threading and Properties” article (part one: http://blog.runserver.net/2008/03/blog-post_28.html) I ran into a case where I needed an atomic function to add a value to a variable passed via an int * pointer (or IntPtr), rather than by ref int. There’s no proper way to convert a pointer into a ref in C#, so I had to turn to P/Invoke. The site http://pinvoke.net offers the following declaration:

[DllImport("kernel32.dll")]
static extern int
InterlockedExchangeAdd(ref int Addend, int Value);

That one doesn’t quite fit our needs, but knowing a few things about pointer marshaling, we can just as well do this:

[DllImport("kernel32.dll")]
static extern int
InterlockedExchangeAdd(int* Addend, int Value);

The method works fine, everything’s fine with it, except for one “small” detail: in x64 mode we get a System.EntryPointNotFoundException, saying that no entry point with that name was found in kernel32.dll. I already mentioned that the Interlocked methods are simply absent from the x64 version of kernel32.dll. Going back to WinBase.h again, we see that this time the methods aren’t hidden behind inline implementations, but are instead forwarded to intrinsic functions (http://msdn2.microsoft.com/en-us/library/191ca0sk.aspx). I couldn’t find exactly where their implementation lives. It’s not in the Platform SDK’s .lib files, nor in the system libraries. Let’s just assume their implementation is baked into the compiler, or somewhere else. The only option I found was to create my own DLL that exports a wrapper function:

extern "C" __declspec(dllexport) LONG
interlockedExchangeAdd(LONG volatile * target, LONG value)
{
    return InterlockedExchangeAdd(target, value);
}

There’s an extra complication: you need to keep two separate libraries, one for x86 mode and one for x64. I worked around this limitation like this:

[DllImport("kernel32.dll",
EntryPoint = "InterlockedExchangeAdd")]
private static extern int
NativeInterlockedExchangeAdd(int * target, int value);

[DllImport("InterlockedWrapper_x64.dll",
EntryPoint = "interlockedExchangeAdd")]
private static extern int
CustomInterlockedExchangeAdd(int * target, int value);

public static int
InterlockedExchangeAdd(int* target, int value)
{
if (IntPtr.Size == 4) // x86
    return NativeInterlockedExchangeAdd(target, value);
else
    return CustomInterlockedExchangeAdd(target, value);
}

So, in x86 mode kernel32.dll is used, while in x64 mode our own wrapper library is used instead.

Update: The blog doesn’t handle long lines well, so I added a few extra line breaks to improve readability.