Interlocked.CompareExchange missing for uint, ulong and (if possible) general structs.

[jkotas]

From @redknightlois on May 18, 2017 19:47

I recently needed to use Interlocked.CompareExchange inside a function with the following form:

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private bool TryClaimSlot(ref uint entryKey, int key)
        {
            var entryKeyValue = entryKey;
            //zero keys are claimed via hash
            if (entryKeyValue == 0 & key != 0)
            {
                entryKeyValue = Interlocked.CompareExchange(ref entryKey, key, 0);
                if (entryKeyValue == 0)
                {
                    // claimed a new slot
                    this.allocatedSlotCount.Increment();
                    return true;
                }
            }

            return key == entryKeyValue;
        }

problem is that it can´t be done because the Interlocked.CompareExchange<T> requires it to be a class.

Also if anyone knows a workaround for it, I would appreciate it.

Copied from original issue: dotnet/coreclr#11723

[jkotas]

From @stephentoub on May 18, 2017 20:22

workaround

For uint, you could do something like:

static unsafe uint InterlockedCompareExchange(ref uint location, uint value, uint comparand)
{
    fixed (uint* ptr = &location)
    {
        return (uint)Interlocked.CompareExchange(ref *(int*)ptr, (int)value, (int)comparand);
    }
}

For ulong, same but with long instead of int overload.

For structs, not sure how that would work given platform limitations on what sizes can be worked with atomically, alignment, etc.

[jkotas]

From @stephentoub on May 18, 2017 20:24

(And with System.Runtime.CompilerServices.Unsafe, you could do the same thing for uint/ulong but without the unsafe pointer stuff: https://github.com/dotnet/corefx/blob/master/src/System.Runtime.CompilerServices.Unsafe/ref/System.Runtime.CompilerServices.Unsafe.cs#L19)

[jkotas]

From @redknightlois on May 18, 2017 21:59

Great! Gonna use that.

[jkotas]

From @danmosemsft on May 20, 2017 2:15

Do we still need an issue? Is there a proposal to add such API?

[jkotas]

From @redknightlois on May 22, 2017 13:20

It feels strange that uint and ulong are not treated as first class citizens in Interlocked methods. So yes, the proposal is to add them.

[jkotas]

From @stephentoub on May 22, 2017 13:46

It feels strange that uint and ulong are not treated as first class citizens

I expect it's because they're not CLS compliant.

[danmoseley]

@redknightlois is this still relevant to you, do you want to write this up as a formal API proposal, per instructions in /Documentation?

[Joe4evr]

@redknightlois Just as a bit of clarification regarding the other part of the title: General structs can't be supported with Interlocked because they can be larger than what a single memory cycle can update, meaning another thread could observe a torn value if it happens to read right in between writes. #17975 seeks to mitigate this problem. Meanwhile, classes don't suffer from this limitation because that is done by a simple reference swap.

[redknightlois]

I have used the workaround, I am more worried about the Interlocked call being an FCALL (I opened an issue for that too).
I remember having seeing a research paper that explains how to do it for general structs, but it is a fair restriction. Nonetheless the suggestion for uint and ulong stands, it looks strange that you have to go on hops for something that should be supported as they are both primitive types.

[redknightlois]

@danmosemsft found a couple more nuisances in the API of interlocked lately.

Say you have a struct like this:

[StructLayout(LayoutKind.Sequential, Size = 128)]
private struct Container
{
    public MemoryBlock* Block1;
    public MemoryBlock* Block2;
    public MemoryBlock* Block3;
    public MemoryBlock* Block4;
}

And now you have that in memory and need to swap atomically the content.

ref Container bucket = ref _containers[threadId];
Interlocked.CompareExchange(bucket.Block1, null, bucket.Block1);

That does not work because there is no Interlocked.CompareExchange( void* ptr, void* ptr, void* ptr ) available.

Probably there is a workaround but I couldnt find it. Anyway, posting it here because it is kinda related to the general shortcomings of the Interlocked API with primitive types like pointers.

PS: Point me to how to write a formal API request and I would do it.

[jkotas]

there is a workaround

You can get the void* overload by casting the void* to IntPtr and calling the IntPtr overload:

static void* CompareExchange(void* ptr, void* ptr, void* ptr) => (void*)Interlocked.CompareExchange(ref *(IntPtr*)ptr, (IntPtr)ptr, (IntPtr)ptr);

I do not think that this API would actually do what you want in your example. You would have to still wrap it with extra goo using fixed or S.R.CS.Unsafe.

[redknightlois]

Actually no, the workaround doesn't work at all.

That's how my examples would look in actual code. ref *(IntPtr*)ptr can be null therefore trying to dereference it would bring up an ReferenceNullException.

Now containter.Block1 content is null, that dereference would happen over a null pointer, which is not the use case either, I need the address of container.Block1 not its content.

if (Interlocked.CompareExchange(ref *(IntPtr*)container.Block1, (IntPtr)header, IntPtr.Zero) == (IntPtr)header)
    return;

The closest thing I could achieve is:

var ptr = new IntPtr(container.Block1);
if (Interlocked.CompareExchange(ref ptr, IntPtr.Zero, (IntPtr)header) == IntPtr.Zero)
    return;

which also doesnt work either, because not ptr is a local variable and it gets swapped instead of the actual reference to container.Block1. Couldn't get anything sensible either using any Unsafe method, and 2.1 has plenty of those :D

Any help would be appreciated, if I cannot make it work, I have to come back to the design board for the entire thing.

[jkotas]

Actually no, the workaround doesn't work at all.

Right, it means that Interlocked.CompareExchange(void* ptr, void* ptr, void* ptr) would not have really solved your problem.

Any help would be appreciated

Try this:

    fixed (Bucket * b = &bucket)
       if (Interlocked.CompareExchange(ref *(IntPtr*)&(b->Block1), IntPtr.Zero, (IntPtr)header) == IntPtr.Zero)
           return;

Another option is to use IntPtr for your fields, and cast them to MemoryBlock* on access. Something like:

private struct Container
{
    private IntPtr _block1;
    private IntPtr _block2;
    private IntPtr _block3;
    private IntPtr _block4;

    public MemoryBlock* Block1 => (MemoryBlock*)_block1;
    public MemoryBlock* Block2 => (MemoryBlock*)_block2;
    public MemoryBlock* Block3 => (MemoryBlock*)_block3;
    public MemoryBlock* Block4 => (MemoryBlock*)_block4;

....
}

Then you can use Interlocked.CompareExchange without the fixed.

[GrabYourPitchforks]

Just to clarify, is the API proposal here that we go through all members of the Interlocked class, adding ref uint / ref ulong overloads where ref int / ref long overloads currently exist?

I assume we'd do the same for ref UIntPtr / ref IntPtr as well since the nuint / nint feature is expected to come online in the near future?

[GrabYourPitchforks]

API proposal:

    public static partial class Interlocked
    {
        /* partial list of existing APIs, for reference */

        public static int Add(ref int location1, int value) { throw null; }
        public static long Add(ref long location1, long value) { throw null; }
        public static int CompareExchange(ref int location1, int value, int comparand) { throw null; }
        public static long CompareExchange(ref long location1, long value, long comparand) { throw null; }
        public static System.IntPtr CompareExchange(ref System.IntPtr location1, System.IntPtr value, System.IntPtr comparand) { throw null; }
        public static int Decrement(ref int location) { throw null; }
        public static long Decrement(ref long location) { throw null; }
        public static int Exchange(ref int location1, int value) { throw null; }
        public static long Exchange(ref long location1, long value) { throw null; }
        public static System.IntPtr Exchange(ref System.IntPtr location1, System.IntPtr value) { throw null; }
        public static int Increment(ref int location) { throw null; }
        public static long Increment(ref long location) { throw null; }
        public static long Read(ref long location) { throw null; }

        /* new proposed APIs, pretty much a carbon copy of the above but unsigned */
        /* all of these would be marked [CLSCompliant(false)] */

        public static uint Add(ref uint location1, uint value) { throw null; }
        public static ulong Add(ref ulong location1, ulong value) { throw null; }
        public static uint CompareExchange(ref uint location1, uint value, uint comparand) { throw null; }
        public static ulong CompareExchange(ref ulong location1, ulong value, ulong comparand) { throw null; }
        public static System.UIntPtr CompareExchange(ref System.UIntPtr location1, System.UIntPtr value, System.UIntPtr comparand) { throw null; }
        public static uint Decrement(ref uint location) { throw null; }
        public static ulong Decrement(ref ulong location) { throw null; }
        public static uint Exchange(ref uint location1, uint value) { throw null; }
        public static ulong Exchange(ref ulong location1, ulong value) { throw null; }
        public static System.UIntPtr Exchange(ref System.UIntPtr location1, System.UIntPtr value) { throw null; }
        public static uint Increment(ref uint location) { throw null; }
        public static ulong Increment(ref ulong location) { throw null; }
        public static ulong Read(ref ulong location) { throw null; }
    }

[terrajobst]

Video

• Makes sense, we added unsigned for the APIs approved in Add bit manipulation methods to Interlocked class #23819
• Let's ignore the generic struct here; this should be a separate proposal
• We should probably add Interlocked support for nint and nuint support on Interlocked. @tannergooding, could you file a tracking item for this?

namespace System.Threading
{
    public static partial class Interlocked
    {
        // New proposed APIs, pretty much a carbon copy of the above but unsigned
        // All of these would be marked [CLSCompliant(false)]

        public static uint Add(ref uint location1, uint value);
        public static ulong Add(ref ulong location1, ulong value);
        public static uint CompareExchange(ref uint location1, uint value, uint comparand);
        public static ulong CompareExchange(ref ulong location1, ulong value, ulong comparand);
        public static UIntPtr CompareExchange(ref UIntPtr location1, UIntPtr value, UIntPtr comparand);
        public static uint Decrement(ref uint location);
        public static ulong Decrement(ref ulong location);
        public static uint Exchange(ref uint location1, uint value);
        public static ulong Exchange(ref ulong location1, ulong value);
        public static UIntPtr Exchange(ref UIntPtr location1, UIntPtr value);
        public static uint Increment(ref uint location);
        public static ulong Increment(ref ulong location);
        public static ulong Read(ref ulong location);

        // Since these were approved in #23819 we should add them:
        // All of these would be marked [CLSCompliant(false)]

        public static int And(ref uint location1, uint value);
        public static long And(ref ulong location1, ulong value);
        public static int Or(ref uint location1, uint value);
        public static long Or(ref ulong location1, ulong value);
        public static int Xor(ref uint location1, uint value);
        public static long Xor(ref ulong location1, ulong value);
    }
}

[tannergooding]

@stephentoub, we should probably clarify that Xor wasn't added in #32216

I'm not sure I like that we added the first two (And and Or), but not the third; as they usually come together (even if we didn't have an immediate use case in the framework).

[stephentoub]

as they usually come together

There are lots of other operations that weren't included. What about Interlocked.Not, for example? Interlocked.Mul? Interlocked.EverythingCsharpHasAnOperatorFor?

We should only add methods when there's a demonstrated need. I've never seen C# code that needed Interlocked.Xor; if such a need appears, we can add it then.

[tannergooding]

What about Interlocked.Not

It wasn't part of the API review.

Interlocked.Mul? Interlocked.EverythingCsharpHasAnOperatorFor?

Not supported by most/any hardwar:

• x86 supports: ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG
• Arm64 supports basically the same, but also atomic min, max

We should only add methods when there's a demonstrated need.

I think there is a slight difference when it comes to "primitive" operations. Interlocked operations are some of the most basic operations on top of which other threading/locking algorithms are implemented.
Providing them gives a foundation on which other things can be built (and which certain things cannot be built without them)

[stephentoub]

It wasn't part of the API review.

My point was that there are lots of other things beyond these. And/Or are used. There was no benefit in Xor being included, and we didn't spend time in API review discussing the merits of each individually; we should in the future.

Not supported by most/any hardwar

So? This isn't about hardware support. These APIs were checked in without hardware support. We can ship the product without hardware support.

Providing them gives a foundation on which other things can be built

.NET has existed for almost 20 years without these variants. We shouldn't be adding effectively dead code until it'll actually be used.

[tannergooding]

we didn't spend time in API review discussing the merits of each individually; we should in the future.

I agree. I think we should try to bring these points up in API review so we don't approve and then immediately turn around and not implement them.

.NET has existed for almost 20 years without these variants.

While I don't know of any usages in the framework, a search shows there are various existing usages of equivalents from other languages/frameworks. For example InterlockedXor (C++ Intrinsic and HLSL for GPU compute) or atomic::fetch_xor (C++ stdlib, similar exists in other languages like JS, Java, and Rust), so there are valid scenarios under which Interlocked.Xor could be used in .NET.

So? This isn't about hardware support

Right, and you don't need anything except CompareExchange support of the appropriate size (to prevent tearing) for most single operations to be implemented.

But, I think hardware support is a reasonable baseline for what other languages/frameworks implement and expose. It also represents something that users cannot implement themselves, as we don't have a way for users to emit something like lock xor or ldeor without the JIT intrinsifying some method (indirect calls and while loops using cmpxchg add overhead and can be non beneficial, but are still better than nothing).

[stephentoub]

I think we should try to bring these points up in API review so we don't approve and then immediately turn around and not implement them.

Agreed. In this case, when I actually looked at it, I turned around and asked the dev that proposed the API, and he agreed we could do without it.

It also represents something that users cannot implement themselves

Sure. But even per your list, And/Or/Xor was incomplete in this regard. If the goal is completeness as compared to some set of hardware primitives, that should be a separate issue. From my perspective, this issue was about something actually being needed, and I see no evidence that C# developers are clamoring for Interlocked.Xor. In contrast, I've seen a multitude of projects implement their own And/Or, including some of ours.

a search shows there are various existing usages of equivalents from other languages/frameworks

Any in C#?

[tannergooding]

Any in C#?

Not that immediately popped up in a search. Most of the results were around the C++ intrinsic and grepping code for sequence of ^ followed by a CompareExchange isn't exactly easy 😄

Sure. But even per your list, And/Or/Xor was incomplete in this regard. If the goal is completeness as compared to some set of hardware primitives, that should be a separate issue. From my perspective, this issue was about something actually being needed, and I see no evidence that C# developers are clamoring for Interlocked.Xor. In contrast, I've seen a multitude of projects implement their own And/Or, including some of ours.

I think that is reasonable. There were others (like atomic bitwise set/complement/reset) which were mentioned during the review that we likewise said should be in a separate "completeness" proposal.

[redknightlois]

From my perspective, this issue was about something actually being needed, and I see no evidence that C# developers are clamoring for Interlocked.Xor. In contrast, I've seen a multitude of projects implement their own And/Or, including some of ours.

Most people that need atomic Xor won't be clamoring for it, those that don't have them just disregard certain types of high-performance algorithms that require them. It is a completeness issue, no one will clamor for anything that they cannot implement; most will just throw their hands in the air, and you won't hear a thing. Having said so, I haven't stumbled on an algorithm that uses XOR atomically, but probably the reason is that as there are not many providing implementations of it, because it is a very niche thing today. For the long term, completeness is always best for a platform, but if that delays the current proposal, I would just go with the partial one.

[jkotas]

algorithm that uses XOR atomically, but probably the reason is that as there are not many providing implementations of it

If you need atomic XOR (or any other bit transformation), you can trivially implement it using CompareExchange. Compared to the specialized atomic instructions, the implementation using CompareExchange is not that much slower to make it a deal breaker.

[stephentoub]

Most people that need atomic Xor won't be clamoring for it

If they "need" it, they'll implement it (CompareExchange loop... and if they can't implement it, personally I'd prefer they not be trying to use lock-free code and the Interlocked type at all). That's what I meant by clamoring for it. Can you please point to real C# examples where someone implemented it? If not, adding such a method in the name of completeness is just adding functionality that'll need to be implemented/tested/documented/maintained/shipped/taking up space/etc. for zero actual benefit. If/when such need is demonstrated in the future, it can be added.

[sunkin351]

If you guys are gonna be adding unsigned variants to Interlocked, may I suggest that you add some sort of atomic Subtraction method? At least for unsigned, as its not too obvious as to how to do that without a subtraction method...