C#•10mo ago

Threadsafety and Interlocked.CompareExchange

Hey, i have written a method that updates a dictionary without locks. Of course i have written a test for it and it succeeded for 15 runs. But today i executed all tests and suddendly the test failed, which i cannot reproduce a second time. Can you guys spot what i might have done wrong?

class UpdateQueueStatus
{
    private static Dictionary<string, UpdateQueueStatus> _mappings = new(StringComparer.OrdinalIgnoreCase);

    public static readonly UpdateQueueStatus None = Create(0);
    public static readonly UpdateQueueStatus Pending = Create(1);
    public static readonly UpdateQueueStatus Queued = Create(0);
    public static readonly UpdateQueueStatus Enqueued = Create(1);
    public static readonly UpdateQueueStatus Caching = Create(2);
    public static readonly UpdateQueueStatus Cached = Create(3);
    public static readonly UpdateQueueStatus Applying = Create(4);
    public static readonly UpdateQueueStatus Applied = Create(5);
    public static readonly UpdateQueueStatus Completed = Create(6);
    public static readonly UpdateQueueStatus Failed = Create(7);
    public static readonly UpdateQueueStatus Cancelled = Create(8);
    public static readonly UpdateQueueStatus Downloading = Create(2);

    public string Value { get; }

    public UpdateQueueStatus(string value)
    {
        Value = value;
    }


    public static UpdateQueueStatus Parse(string value)
    {
        if (_mappings.TryGetValue(value, out var status))
        {
            return status;
        }

        var result = new UpdateQueueStatus(value);

        while (true)
        {
            var currentMap = _mappings;

            var newMap = new Dictionary<string, UpdateQueueStatus>(currentMap, StringComparer.OrdinalIgnoreCase);
            newMap.TryAdd(value, result);
            if (Interlocked.CompareExchange(ref _mappings, newMap, currentMap) == currentMap)
            {
                break;
            }
        }

        return result;
    }

    private static UpdateQueueStatus Create(int number, [CallerMemberName] string? name = null)
    {
        var result = new UpdateQueueStatus(name ?? "None");
        _mappings.TryAdd(number.ToString(), result);
        _mappings.TryAdd(result.Value, result);
        _intMappings.Add((result.Value, number));
        return result;
    }
}

// Test:

public class Test
{
    [Fact]
    public void Should_Be_Threadsafe()
    {
        var count = UpdateQueueStatus.GetMappings().Count;

        var tasks = new List<Task>();
        for (int i = 0; i < 100; i++)
        {
            var task = Task.Run(() =>
            {
                for (int j = 0; j < 100; j++)
                {
                    UpdateQueueStatus.Parse("value" + j);
                }
            });
            tasks.Add(task);
        }
        Task.WaitAll(tasks.ToArray());

        //Console.WriteLine("Number of keys in the dictionary: " + UpdateQueueStatus.GetMappings());
        Assert.Equal(count + 100, UpdateQueueStatus.GetMappings().Count);
    }
}

class UpdateQueueStatus
{
    private static Dictionary<string, UpdateQueueStatus> _mappings = new(StringComparer.OrdinalIgnoreCase);

    public static readonly UpdateQueueStatus None = Create(0);
    public static readonly UpdateQueueStatus Pending = Create(1);
    public static readonly UpdateQueueStatus Queued = Create(0);
    public static readonly UpdateQueueStatus Enqueued = Create(1);
    public static readonly UpdateQueueStatus Caching = Create(2);
    public static readonly UpdateQueueStatus Cached = Create(3);
    public static readonly UpdateQueueStatus Applying = Create(4);
    public static readonly UpdateQueueStatus Applied = Create(5);
    public static readonly UpdateQueueStatus Completed = Create(6);
    public static readonly UpdateQueueStatus Failed = Create(7);
    public static readonly UpdateQueueStatus Cancelled = Create(8);
    public static readonly UpdateQueueStatus Downloading = Create(2);

    public string Value { get; }

    public UpdateQueueStatus(string value)
    {
        Value = value;
    }


    public static UpdateQueueStatus Parse(string value)
    {
        if (_mappings.TryGetValue(value, out var status))
        {
            return status;
        }

        var result = new UpdateQueueStatus(value);

        while (true)
        {
            var currentMap = _mappings;

            var newMap = new Dictionary<string, UpdateQueueStatus>(currentMap, StringComparer.OrdinalIgnoreCase);
            newMap.TryAdd(value, result);
            if (Interlocked.CompareExchange(ref _mappings, newMap, currentMap) == currentMap)
            {
                break;
            }
        }

        return result;
    }

    private static UpdateQueueStatus Create(int number, [CallerMemberName] string? name = null)
    {
        var result = new UpdateQueueStatus(name ?? "None");
        _mappings.TryAdd(number.ToString(), result);
        _mappings.TryAdd(result.Value, result);
        _intMappings.Add((result.Value, number));
        return result;
    }
}

// Test:

public class Test
{
    [Fact]
    public void Should_Be_Threadsafe()
    {
        var count = UpdateQueueStatus.GetMappings().Count;

        var tasks = new List<Task>();
        for (int i = 0; i < 100; i++)
        {
            var task = Task.Run(() =>
            {
                for (int j = 0; j < 100; j++)
                {
                    UpdateQueueStatus.Parse("value" + j);
                }
            });
            tasks.Add(task);
        }
        Task.WaitAll(tasks.ToArray());

        //Console.WriteLine("Number of keys in the dictionary: " + UpdateQueueStatus.GetMappings());
        Assert.Equal(count + 100, UpdateQueueStatus.GetMappings().Count);
    }
}

Test failure:

The test failed:
Message: 
Assert.Equal() Failure
Expected: 125
Actual: 121

The test failed:
Message: 
Assert.Equal() Failure
Expected: 125
Actual: 121

32 Replies

nathanAjacobs•10mo ago

Why not just use a ConcurrentDictionary?

cap5lut•10mo ago

that spin update looks correct to me, the thing is, u have pre-populated the dictionary with data, can u show how u do that? it might also be a problem because its all static, thus other tests might affect the results (one of the reasons why mutable static states arent really recommended)

PloxiOP•10mo ago

Sure. Updated post Really just one test is testing this particular class Because Dictionary is faster and the add is a not-so-happy path which really should'nt happen in the first place

cap5lut•10mo ago

how is the Value property set?

PloxiOP•10mo ago

the constructor sets it new UpdateQueueStatus(value) Updated post

cap5lut•10mo ago

hmmm, i dont see where its going wrong, but its basically all we need to see 🤔 im not sure how its with dotnet, but it might be that u need to make _mappings volatile (btw, the naming convention suggest for static private members s_ as prefix)

PloxiOP•10mo ago

oh thanks for the volatile, that might be it... s_ is ugly xDDD

cap5lut•10mo ago

that spin loop to update is in the end correct and the rest of the code doesnt seem to be at fault either

PloxiOP•10mo ago

yea the spin loop was the hardest thing to understand 😄 Ran the tests 10 times now and no error....

cap5lut•10mo ago

btw if newMap.TryAdd(value, result); returns false u can already stop the spinning cant ya?

PloxiOP•10mo ago

good point! thank you!

cap5lut•10mo ago

and, if u have a lot of simultaneous concurrent writes all the time, this will be a nightmare for the gc

PloxiOP•10mo ago

xD but i wont have those

cap5lut•10mo ago

actually not the gc, but the whole copying the data over

PloxiOP•10mo ago

cause parsing when the _mappings dont have an entry is the super unhappy path like every state should already be known

cap5lut•10mo ago

usually if u have lock-free stuff like that ur data structures are node based so that u simply have to replace 1-2 nodes, u are doing full copies aah, so its just at start that there is contentation, yeah then this makes sense question is if volatile will really fix this or not

PloxiOP•10mo ago

57 tests passed

cap5lut•10mo ago

the only really accurate result u can get is that the test fails, else its just guessing

PloxiOP•10mo ago

The static initializer initializes all known states. There are currently no unknowns. Unknowns (aka Parse adds to the map) will only happen when the caller is "newer", so i dont have to touch every program when implementing a new state

cap5lut•10mo ago

is ur UpdateQueueStatus.GetMappings() a simple return _mappings; btw?

PloxiOP•10mo ago

yes

cap5lut•10mo ago

yeah then volatile should fix this

PloxiOP•10mo ago

    #region UnitTestCode
    [Obsolete("Do not use, only for test")]
    [EditorBrowsable(EditorBrowsableState.Never)]
    [Browsable(false)]
    internal static Dictionary<string, UpdateQueueStatus> GetMappings() => _mappings;


    #endregion

    #region UnitTestCode
    [Obsolete("Do not use, only for test")]
    [EditorBrowsable(EditorBrowsableState.Never)]
    [Browsable(false)]
    internal static Dictionary<string, UpdateQueueStatus> GetMappings() => _mappings;


    #endregion

EditorBrowseable is so useless when the caller is in the same project thats why Obsolete: Scream at them not to use it 😄

cap5lut•10mo ago

i asked in #allow-unsafe-blocks , lets see what they say, they have deeper insight than me can u write another unit test without having the volatile on it yet? basically

void Test()
{
  for (int i = 0; i < 50; i++) Should_Be_Threadsafe();
  Thread.Sleep(1000);
  for (int i = 0; i < 50; i++) Should_Be_Threadsafe();
}

void Test()
{
  for (int i = 0; i < 50; i++) Should_Be_Threadsafe();
  Thread.Sleep(1000);
  for (int i = 0; i < 50; i++) Should_Be_Threadsafe();
}

PloxiOP•10mo ago

Succeeds I will extract the map parts out into a nonstatic class and test that one

cap5lut•10mo ago

regarding https://discord.com/channels/143867839282020352/312132327348240384/1204778384236879872

MODiX•10mo ago

Ploxi

I have tested it extensively without volatile (50 times) and it didnt fail. Ran the whole test project for unrelated reasons and this test failed. Ran it again and it didnt fail. Have added volatile and ran the test 400 times and it never failed in this run

Quoted by

<@233139962277658624> from #allow-unsafe-blocks (click here)

React with ❌ to remove this embed.

cap5lut•10mo ago

u could run the tests all day, turn ur computer into an oven and it doesnt fail, but still could occasionally i need to read up how volatile works in dotnet/if its the same/similar to java

cap5lut•10mo ago

instead of marking it as volatile it seems u should use Volatile.Read<T>(ref T) instead

Volatile.Read Method (System.Threading)

Reads the value of a field. On systems that require it, inserts a memory barrier that prevents the processor from reordering memory operations as follows: If a read or write appears after this method in the code, the processor cannot move it before this method.

cap5lut•10mo ago

...to make it completely safe even for multi processor systems

PloxiOP•10mo ago

Do i only need volatile.read in the threadsafe add? Like so?

    public void AddThreadSafe(string key, TStatus value)
    {
        while (true)
        {
            var currentMap = Volatile.Read(ref _mappings);

            var newMap = new Dictionary<string, TStatus>(currentMap, StringComparer.OrdinalIgnoreCase);

            // true, if another thread added the value already
            var hasAdded = !newMap.TryAdd(key, value);
            if (hasAdded || Interlocked.CompareExchange(ref _mappings, newMap, currentMap) == currentMap)
            {
                break;
            }
        }
    }

    public void AddThreadSafe(string key, TStatus value)
    {
        while (true)
        {
            var currentMap = Volatile.Read(ref _mappings);

            var newMap = new Dictionary<string, TStatus>(currentMap, StringComparer.OrdinalIgnoreCase);

            // true, if another thread added the value already
            var hasAdded = !newMap.TryAdd(key, value);
            if (hasAdded || Interlocked.CompareExchange(ref _mappings, newMap, currentMap) == currentMap)
            {
                break;
            }
        }
    }

cap5lut•10mo ago

nah, in the getter instead of var hasAdded = !newMap.TryAdd(key, value); u can simply write if (!newMap.TryAdd(key, value)) return; by getter i mean GetMappings()

Gaming

Programming

Threadsafety and Interlocked.CompareExchange