Last-write win problem when hash colision happens

[lyra95]

Hello,

I think the example below is quite clear but let me explain how I found the issue.

I'm using stashbox in a production service(it is a ASP.NET server). Recently, I had issues that a ASP controller is unable to be resolved and that controller hasn't changed any for last year. After few hours of debugging, I found out that controller has the exact same hash with some other completely unrelated transient type. Also found that the controller is missing when I looked up GetRegistrationMappings().

I'm not sure but I guess some edge cases are mishandled in the implementation of ImmutableTree<>?

Version

The issue can also be reproduced in the latest stashbox/dotnet but just in case:

• dotnet runtiem/sdk : 7.0.407
• Stashbox.Extensions.Hosting : 4.6.0

Minimal Reproducible Example

https://dotnetfiddle.net/regFlE

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using Stashbox;

public class Program
{
    public static void Main()
    {
        var (type1, type2) = GetCollidingTypes();

        // they're different
        Debug.Assert(type1!=type2);
        // but their hashes are the same
        Debug.Assert(System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(type1)==System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(type2));

        var services = new StashboxContainer();
        services.Register(type1);
        services.Register(type2);

        services.Resolve(type2); // this succeeds as the last-write wins
        services.Resolve(type1); // this fails, "unable to resolve type"
    }

    private static (Type, Type) GetCollidingTypes()
    {
        var hashes = new Dictionary<int, Type>();
    uint n = 0;
        while (true)
        {
            var type = GenerateType(n++);
            var hash = System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(type);
            if (hashes.ContainsKey(hash))
            {
                return (hashes[hash], type);
            }

            hashes.Add(hash, type);
        }

        throw new InvalidOperationException("unreachable");
    }

    private static Type GenerateType(uint n)
    {
        var current = typeof(Nil);
        for (var i=0; i < sizeof(uint) * 8; i++)
        {
            var leading = n >> i;
            if (leading == 0) {
                return current;
            }

            var bit = (n >> i) & 0x01;
            if (bit == 0) {
                current = typeof(Zero<>).MakeGenericType(current);
            } else {
                current = typeof(One<>).MakeGenericType(current);
            }
        }
        return current;
    }
}

internal class Nil {}
internal class Zero<T> {}
internal class One<T> {}

[z4kn4fein]

Hi @lyra95, thank you for reporting this issue! I will check this out and let you know when the fix is ready.

[z4kn4fein]

Hi @lyra95, I've released the fix in Stashbox v5.14.1 and Stashbox.Extensions.Hosting v.5.5.2. Thank you for the report again, and sorry for the inconvenience this issue caused!

[lyra95]

The issue has been resolved after updating to Stashbox.Extensions.Hosting v5.5.2. Thank you for the swift fix, it's been a great experience using stashbox so far!

Just one question before closing: I think the implementation could have been simpler if immutable collections in standard library were used instead. Is there a particular reason implementing Immutable tree/buckets? I'm not intending to be critical, but just curious about it.

[z4kn4fein]

Thank you for your appreciation!

I decided (some major versions ago) to use custom immutable data structures purely because of performance considerations.

Here's a current benchmark of ImmutableTree<Type, string> vs ImmutableDictionary<Type, string>:

BenchmarkDotNet=v0.13.5, OS=Windows 10 (10.0.19045.4170/22H2/2022Update)
AMD Ryzen 9 7950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK=8.0.103
  [Host]     : .NET 8.0.3 (8.0.324.11423), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.3 (8.0.324.11423), X64 RyuJIT AVX2

Method	Count	Mean	Error	StdDev
ImmutableDictionary_Add	10	900.38 ns	9.854 ns	9.218 ns
ImmutableTree_AddOrUpdate	10	279.62 ns	3.565 ns	3.335 ns
ImmutableDictionary_TryGetValue	10	67.48 ns	0.964 ns	0.902 ns
ImmutableTree_GetOrDefault	10	20.29 ns	0.143 ns	0.126 ns
ImmutableDictionary_Add	100	18,253.55 ns	200.641 ns	177.863 ns
ImmutableTree_AddOrUpdate	100	6,522.42 ns	113.359 ns	106.036 ns
ImmutableDictionary_TryGetValue	100	845.75 ns	14.979 ns	13.278 ns
ImmutableTree_GetOrDefault	100	373.13 ns	6.221 ns	5.819 ns
ImmutableDictionary_Add	1000	314,795.38 ns	4,048.352 ns	3,786.831 ns
ImmutableTree_AddOrUpdate	1000	116,336.24 ns	1,955.322 ns	1,829.009 ns
ImmutableDictionary_TryGetValue	1000	11,684.09 ns	126.399 ns	118.233 ns
ImmutableTree_GetOrDefault	1000	6,609.47 ns	100.771 ns	94.261 ns

[lyra95]

Thanks for the detailed information!