ConcurrentTLru leaks memory in removed element's values

[snaumenko-st]

In our application we use Async, Atomic ConcurrentTLru implementation for caching very large 128MB string values.
And we found that these values remain referenced from inside the cache even after they are removed from it.
Investigation showed that after item is removed from dictionary it still remains in Lru queues until full cycle is performed and it's evicted out from cold queue.
The cycling logic also doesn't pay attention to the WasRemoved field of the item and continues to move it between queues.

My suggestion is:

• implement IDisposable on AsyncAtomicFactory and similar classes to dispose internal values and set them to default on remove from dictionary.
• change cycling logic so that it will respect WasRemoved field and evict item from Lru ASAP.

[bitfaster]

Thanks for reporting this.

The WasRemoved thing looks like an obvious bug now I read through the code - I will take a look at this on the weekend. It is several years since I wrote it so it's not fresh in my mind, this is my take reading through it just now:

• WasRemoved indicates the item is removed from the dictionary, but present in the queues.
• IItemPolicy.ShouldDiscard is called after dictionary lookups. At this point should discard doesn't need to check WasRemoved, because the flag is only set after removing from the dictionary. If there was a race and the item was removed after the lookup but before should discard was called, we can still return the value because value has not been set to default as part of the remove. I consider this a benign race where the caller could not reasonably tell what order these events occurred in.
• IItemPolicy.RouteX family of methods determine which queue to move the item to, or whether to delete it. At some point I think I did a refactoring to make route call ShouldDiscard to dedupe code, and I suspect at that point introduced this bug thinking I did something smart.
• I need to check whether I can simply return ItemDestination.Remove from the route methods, which would more eagerly remove items from the queue during cycle. This is what I thought was happening before I read just now.

As a workaround, if you don't want to use scoped + IDisposble, you can instead use ConcurrentLfu, which does not have this issue (since LFU has a totally different algorithm).

Regarding IDisposable, see docs here. You can use scoped/lifetime to guarantee that cache items are 'alive' (else the cache can return a disposed item to the caller, or dispose an item while the caller is using it). The IDisposable implementation for AsyncAtomicFactory is called ScopedAsyncAtomicFactory. If you release memory via your value's dispose method, only the LruItem will remain in the cache (which is quite small). Obviously, this assumes that the value you put in the cache is IDisposable. This is how I have dealt with large cache objects as you described (typically I am using something like ArrayPool or RecycleableMemoryStream, so I return to the pool on dispose using this mechanism).

Without scoped, setting values to default on remove results in race conditions where it is possible to return a default value from a cache lookup (because the LruItem.Value property can be set to default between retrieving LruItem from the dictionary and returning the value to the caller). I would prefer not to take that change because it could lead to unexpected null refs. This was a deliberate speed tradeoff - current approach makes read lock free. The alternative is to lock the item on read, but this will result in massive lock contention on read - and a significant concurrent throughput decrease when reading the same value.

Regarding setting to default to de-reference the value, assuming you use scoped as described above to avoid races, I suspect the correct place to do that is here. I will take a look at this to see if there is a possible race where default may be returned, but I think that is safe.

 

[snaumenko-st]

Thanks for the detailed explanation!

I tried to use Scoped as you mentioned, and it worked fine. Although I found that it has too much overhead for our use case. We don't use pooled objects, string values are immutable and don't cause any troubles if they are lost somewhere.

I decided to add IDisposable to AsyncAtomicFactory to nullify the value there as as workaround. A simple null check after receiving the value from it deals with the issue just fine in our case.

The inconvenient thing is that if we use pure ConcurrentTLru without async and atomic support, then IDisposable values work as expected, but when the item is wrapped with some internal factory, it stops working except for the case when Scoped is also specified. I think you could take a look into this part as well.

Without scoped, setting values to default on remove results in race conditions where it is possible to return a default value from a cache lookup (because the LruItem.Value property can be set to default between retrieving LruItem from the dictionary and returning the value to the caller)

Is it possible to initialize local var in this case and check it for null then before returning to the caller? It shouldn't have any noticeable overhead IMO.

[bitfaster]

It's legal to cache null reference types or default value types. For example ICache<string, Guid> may legitimately cache Guid.Empty. In this situation, if we check for default before returning, we cannot distinguish between an item that was deleted vs cached as empty. The alternative is to check the WasDeleted flag, but this is not safe without a lock because the two memory addresses can be changed independently and race. To fix that race, both fields would need to be wrapped in an immutable class that gets replaced on delete, this would give atomic read but result in additional allocation/pointer de-ref (i.e. an item within an item).

That aside, I fought pretty hard to eliminate all these small checks in the hot path because they are like a micro tax that shows up in micro benchmarks. I realize this is not the tradeoff for everyone and real-world gains are tiny, but my goal with this library was to make performance first decisions without compromise.

[bitfaster]

I completed a fix to correctly purge removed items when transitioning between the internal queues - this will be included in the next release.

I would not take a fix for the null check as described above. I would not take the fix changing AsyncAtomicFactory to implement IDisposable because it has two consequences:

• ConcurrentLru uses Disposer<T> to elide dispose code for non-disposable values. If AsyncAtomicFactory<T> implements IDisposable, the dispose code will be generated by the JIT even when T is not IDisposable. This is a minor penalty in an edge case.
• Implementing this suggests it is safe to store IDisposable types in caches based on AsyncAtomicFactory<T>. This works in your specific scenario, but in general is prone to races that can produce incorrect results.

[snaumenko-st]

First of all, thank you for your efforts and quick resolution! I truly appreciate it.

But regarding IDisposable, I would still like to comment:

• Perhaps, with the new improvement for faster eviction of cached objects, this may no longer be a major issue. However, clearing data can still be relevant for any objects that are not unmanaged structs and contain a reference to some reference type inside or are themselves a reference type. Instead of focusing on IDisposable, it might be better to consider this criterion specifically. For any unmanaged struct values, this behavior isn't needed, but otherwise, we can't guarantee the lifetime of the data. If data isn't added to the cache frequently (and thus doesn't cycle out), it may remain there for a long time.
  Moreover, regarding the performance question, reference counting for objects will still be handled at the GC level. I have a feeling that by reducing the complexity of reference trees, we can speed up and simplify the GC's work, ultimately reducing the overhead of garbage collection.

• This part is unclear because the documentation explicitly states:

All cache classes in BitFaster.Caching own the lifetime of cached values and will automatically dispose of values when they are evicted."

I agree that in more complex scenarios involving complex objects, using Scoped is the right approach. However, in simpler cases where the user is confident that it's safe, it's not entirely clear to me why the behavior differs depending on the configuration of this component. And in the case of Async and Atomic, it doesn’t work at all.

[bitfaster]

I realized there is an alternative approach which does not require a code change, register an event to eagerly dispose the value when it is evicted:

lru.Events.Value.ItemRemoved += (source, args) => args.Value.Dispose());

The core issue is correctness. If the cached value is IDisposable, the cache can return disposed values resulting in unexpected program state. This can occur in any program with two or more concurrent threads when at least one of them is a writer.

Consider this code which will throw InvalidOperationException immediately on my machine:

public async Task Test()
{
    using var source = new CancellationTokenSource();
    var cache = new ConcurrentLru<int, MyDisposable>(10);

    // 1. background: add and remove the same value
    var t = Task.Run(() => 
    {
        while (!source.Token.IsCancellationRequested)
        {
            cache.AddOrUpdate(0, new MyDisposable());
            cache.TryRemove(0);
        }
    });

    try
    {
        // 2. foreground: read the value and assume it is not disposed
        while (true)
        {
            if (cache.TryGet(0, out var d))
            {
                d.Use();
            }
        }
    }
    finally
    {
        source.Cancel();
        await t;
    }
}

public class MyDisposable : IDisposable
{
    public bool isDisposed = false;
    public void Use() { if (isDisposed) throw new InvalidOperationException(); }
    public void Dispose() {  isDisposed = true; }
}

The statement in the documentation is intended to warn against this (because it is a race, it can be much harder to repro in a real program) - I will update the docs to make it clear that caching IDisposable exposes the caller to such races that can be dangerous.

I agree that the API surface is inconsistent: the caches allow storing IDisposable with no safeguards whereas the wrappers for async/atomic do not. Changing the former is a breaking change, changing the latter increases the likelihood that someone can write incorrect code by accident.

Since there is a workaround, rather than increase the chances of a mistake, I would prefer to keep 'as is'.