ConcurrentLfu.Trim races with AddOrUpdate in 2.6.0 and corrupts the LFU list

[RuneH-MSFT]

Description

ConcurrentLfu can throw a NullReferenceException when Policy.Eviction.Trim runs concurrently with AddOrUpdate.

This appears to be a regression in BitFaster.Caching 2.6.0. The same workload did not reproduce the failure with 2.5.4.

Minimal reproduction

Create a console application:

dotnet new console --framework net10.0
dotnet add package BitFaster.Caching --version 2.6.0

Replace Program.cs with:

using BitFaster.Caching.Lfu;
using BitFaster.Caching.Scheduler;

var cache = new ConcurrentLfu<int, string>(
		Environment.ProcessorCount,
		1_000_000,
		new ForegroundScheduler(),
		EqualityComparer<int>.Default);

for (int i = 0; i < 10_000; i++)
{
		cache.AddOrUpdate(i, "value");
}

Parallel.Invoke(
		() =>
		{
				for (int i = 10_000; i < 1_000_000; i++)
				{
						cache.AddOrUpdate(i, "value");
				}
		},
		() =>
		{
				for (int i = 0; i < 100_000; i++)
				{
						cache.Policy.Eviction.Value!.Trim(8);
				}
		});

Run it in Release mode:

dotnet run --configuration Release

Actual behavior

The failure usually occurs on the first run:

System.AggregateException: One or more errors occurred.
 ---> System.NullReferenceException: Object reference not set to an instance of an object.
	 at BitFaster.Caching.Lfu.LfuNodeList`2.InternalInsertNodeBefore(...)
	 at BitFaster.Caching.Lfu.LfuNodeList`2.AddLast(...)
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.EvictFromWindow()
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.EvictEntries(ItemRemovedReason reason)
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.Maintenance(...)
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.DrainBuffers()
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.TryScheduleDrain()
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.ScheduleAfterWrite()
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.AfterWrite(...)
	 at BitFaster.Caching.Lfu.ConcurrentLfuCore`5.AddOrUpdate(...)

Expected behavior

Concurrent AddOrUpdate and Policy.Eviction.Trim operations should not corrupt the internal LFU lists or throw an exception.

If concurrent use of Trim is intentionally unsupported, it would be useful for that limitation to be documented.

Regression

• 2.5.4: The reproducer completed successfully in 10 consecutive Release runs.
• 2.6.0: The failure reproduces consistently, usually on the first run.
• Observed on both .NET Framework 4.8 and .NET 10.

Suspected cause

The behavior appears to have changed in commit 0686f4e5, which implemented ConcurrentLfu events.

In 2.5.4, Trim selected candidates under maintenanceLock and then called:

TryRemove(candidate.Key);

TryRemove marked the node as removed and queued it through AfterWrite, so the actual LFU list removal occurred later during maintenance under maintenanceLock.

In 2.6.0, Trim calls:

Evict(candidate, reason);

This call occurs after Trim has released maintenanceLock. Evict directly executes:

evictee.list?.Remove(evictee);

A concurrent AddOrUpdate can run foreground maintenance and mutate the same LfuNodeList while this removal is taking place. Remove invalidates the node links, allowing AddLast or EvictFromWindow to dereference a null prev or next link.

One possible fix would be to perform the candidate list removal while holding maintenanceLock, while dispatching removal event callbacks after releasing the lock to avoid callback reentrancy or deadlocks.