6779506517

Committed 07 Nov 2023 03:10AM UTC coverage: 98.277% (-0.5%) from 98.732%

Build # 6779506517

Build Type

push

github

Committed by

web-flow

Commit Message

Fix LRU clear when warm/hot items are touched (#453)

* Fix LRU clear when warm/hot items are touched

* add trim test

* special case

* cleanup

---------

Run Details

858 of 890 branches covered (0.0%)

Branch coverage included in aggregate %.

9 of 9 new or added lines in 1 file covered. (100.0%)

16 existing lines in 3 files now uncovered.

3706 of 3754 relevant lines covered (98.72%)

21189540.55 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.65

/BitFaster.Caching/Atomic/ScopedAsyncAtomicFactory.cs

﻿using System;
using System.Diagnostics;
using System.Threading;
using System.Threading.Tasks;

namespace BitFaster.Caching.Atomic
{
    /// <summary>
    /// A class that provides simple, lightweight exactly once initialization for scoped values
    /// stored in a cache.
    /// </summary>
    /// <typeparam name="K">The type of the key.</typeparam>
    /// <typeparam name="V">The type of the value.</typeparam>
    [DebuggerDisplay("IsScopeCreated={initializer == null}, Value={ScopeIfCreated}")]
    public sealed class ScopedAsyncAtomicFactory<K, V> : IScoped<V>, IDisposable where V : IDisposable
    {
        private Scoped<V> scope;
        private Initializer initializer;

        /// <summary>
        /// Initializes a new instance of the <see cref="ScopedAsyncAtomicFactory{K, V}"/> class.
        /// </summary>
        public ScopedAsyncAtomicFactory()
        {
            initializer = new Initializer();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ScopedAsyncAtomicFactory{K, V}"/> class with the
        /// specified value.
        /// </summary>
        /// <param name="value">The value.</param>
        public ScopedAsyncAtomicFactory(V value)
        {
            scope = new Scoped<V>(value);
        }

        /// <summary>
        /// Gets a value indicating whether the scope has been initialized.
        /// </summary>
        public bool IsScopeCreated => initializer == null;

        /// <summary>
        /// Gets the scope if it has been initialized, else default.
        /// </summary>
        public Scoped<V> ScopeIfCreated
        {
            get
            {
                if (initializer != null)
                {
                    return default;
                }

                return scope;
            }
        }

        /// <summary>
        /// Attempts to create a lifetime for the scoped value. The lifetime guarantees the value is alive until 
        /// the lifetime is disposed.
        /// </summary>
        /// <param name="lifetime">When this method returns, contains the Lifetime that was created, or the default value of the type if the operation failed.</param>
        /// <returns>true if the Lifetime was created; otherwise false.</returns>
        public bool TryCreateLifetime(out Lifetime<V> lifetime)
        {
            if (scope?.IsDisposed ?? false || initializer != null)
            {
                lifetime = default;
                return false;
            }

            return scope.TryCreateLifetime(out lifetime);
        }

        /// <summary>
        /// Attempts to create a lifetime for the scoped value. The lifetime guarantees the value is alive until 
        /// the lifetime is disposed.
        /// </summary>
        /// <param name="key">The key associated with the scoped value.</param>
        /// <param name="valueFactory">The value factory to use to create the scoped value when it is not initialized.</param>
        /// <returns>true if the Lifetime was created; otherwise false. If the lifetime was created, the new lifetime is also returned.</returns>
        // backcompat: remove
        public ValueTask<(bool success, Lifetime<V> lifetime)> TryCreateLifetimeAsync(K key, Func<K, Task<Scoped<V>>> valueFactory)
        {
            return TryCreateLifetimeAsync(key, new AsyncValueFactory<K, Scoped<V>>(valueFactory));
        }

        /// <summary>
        /// Attempts to create a lifetime for the scoped value. The lifetime guarantees the value is alive until 
        /// the lifetime is disposed.
        /// </summary>
        /// <typeparam name="TFactory">The type of the value factory.</typeparam>
        /// <param name="key">The key associated with the scoped value.</param>
        /// <param name="valueFactory">The value factory to use to create the scoped value when it is not initialized.</param>
        /// <returns>true if the Lifetime was created; otherwise false. If the lifetime was created, the new lifetime is also returned.</returns>
        public async ValueTask<(bool success, Lifetime<V> lifetime)> TryCreateLifetimeAsync<TFactory>(K key, TFactory valueFactory) where TFactory : struct, IAsyncValueFactory<K, Scoped<V>>
        {
            // if disposed, return
            if (scope?.IsDisposed ?? false)
            {
                return (false, default);
            }

            // Create scope EXACTLY once, ref count cas operates over same scope
            if (initializer != null)
            {
                await InitializeScopeAsync(key, valueFactory).ConfigureAwait(false);
            }

            bool res = scope.TryCreateLifetime(out var lifetime);
            return (res, lifetime);
        }

        private async ValueTask InitializeScopeAsync<TFactory>(K key, TFactory valueFactory) where TFactory : struct, IAsyncValueFactory<K, Scoped<V>>
        {
            var init = Volatile.Read(ref initializer);

            if (init != null)
            {
                scope = await init.CreateScopeAsync(key, valueFactory).ConfigureAwait(false);
                Volatile.Write(ref initializer, null);
            }
        }

        /// <summary>
        /// Terminates the scope and disposes the value. Once the scope is terminated, it is no longer
        /// possible to create new lifetimes for the value.
        /// </summary>
        public void Dispose()
        {
            var init = initializer;

            if (init != null && init.TryGetScope(out var disposeScope))
            {
                scope = disposeScope;
            }

            // It is possible that a task was running to create the scope, but it didn't complete yet
            // in that case this.scope == null. Initializer is now marked for dispose, and the new 
            // scope will be disposed when the task completes.
            scope?.Dispose();
        }

        private class Initializer
        {
            private bool isTaskInitialized;
            private bool isTaskCompleted;
            private bool isDisposeRequested;
            private Task<Scoped<V>> task;

            public async ValueTask<Scoped<V>> CreateScopeAsync<TFactory>(K key, TFactory valueFactory) where TFactory : struct, IAsyncValueFactory<K, Scoped<V>>
            {
                var tcs = new TaskCompletionSource<Scoped<V>>(TaskCreationOptions.RunContinuationsAsynchronously);

                var synchronizedTask = DoubleCheck(tcs.Task);

                if (ReferenceEquals(synchronizedTask, tcs.Task))
                {
                    try
                    {
                        var scope = await valueFactory.CreateAsync(key).ConfigureAwait(false);
                        tcs.SetResult(scope);

                        Volatile.Write(ref isTaskCompleted, true);

                        if (Volatile.Read(ref isDisposeRequested))
                        {
                            scope.Dispose();
                        }

                        return scope;
                    }
                    catch (Exception ex)
                    {
                        Volatile.Write(ref isTaskInitialized, false);
                        tcs.SetException(ex);
                        throw;
                    }
                }

                return await synchronizedTask.ConfigureAwait(false);
            }

#pragma warning disable CA2002 // Do not lock on objects with weak identity
            private Task<Scoped<V>> DoubleCheck(Task<Scoped<V>> value)
            {
                // Fast path
                if (Volatile.Read(ref isTaskInitialized))
                {
                    return task;
                }

                lock (this)
                {
                    if (!isTaskInitialized)
                    {
                        task = value;
                        isTaskInitialized = true;
                    }
                }

                return task;
            }
#pragma warning restore CA2002 // Do not lock on objects with weak identity

            // <remarks>
            // Let's say there are 2 threads, A and B:
            // A is the init thread
            //    1. mark isTaskInitialized = true
            //    2. read is dispose requested
            // B is the dispose thread
            //    1. mark dispose requested = true
            //    2. read isTaskInitialized
            // Due to the rules of volatile, these reads and writes cannot be reordered. 
            // Therefore, the dispose race reduces to two possible scenarios:
            // 1. If init task is completed, we can return it, then dispose it
            // 2. If it is not yet completed, it is guaranteed to dispose on completion because volatile writes cannot be re-ordered.
            // If the value factory continuously throws, the object will be neither created nor disposed. This is considered benign.
            // </remarks>
            public bool TryGetScope(out Scoped<V> scope)
            {
                Volatile.Write(ref this.isDisposeRequested, true);

                if (Volatile.Read(ref isTaskCompleted))
                {
                    // isTaskCompleted is only set when there is no exception, so this is safe to return
                    scope = task.Result;
                    return true;
                }

                scope = default;
                return false;
            }
        }
    }
}

1	using System;
2	using System.Diagnostics;
3	using System.Threading;
4	using System.Threading.Tasks;
5
6	namespace BitFaster.Caching.Atomic
7	{
8	/// <summary>
9	/// A class that provides simple, lightweight exactly once initialization for scoped values
10	/// stored in a cache.
11	/// </summary>
12	/// <typeparam name="K">The type of the key.</typeparam>
13	/// <typeparam name="V">The type of the value.</typeparam>
14	[DebuggerDisplay("IsScopeCreated={initializer == null}, Value={ScopeIfCreated}")]
15	public sealed class ScopedAsyncAtomicFactory<K, V> : IScoped<V>, IDisposable where V : IDisposable
16	{
17	private Scoped<V> scope;
18	private Initializer initializer;
19
20	/// <summary>
21	/// Initializes a new instance of the <see cref="ScopedAsyncAtomicFactory{K, V}"/> class.
22	/// </summary>
23	public ScopedAsyncAtomicFactory()	15,443✔
24	{	15,443✔
25	initializer = new Initializer();	15,443✔
26	}	15,443✔
27
28	/// <summary>
29	/// Initializes a new instance of the <see cref="ScopedAsyncAtomicFactory{K, V}"/> class with the
30	/// specified value.
31	/// </summary>
32	/// <param name="value">The value.</param>
33	public ScopedAsyncAtomicFactory(V value)	99✔
34	{	99✔
35	scope = new Scoped<V>(value);	99✔
36	}	99✔
37
38	/// <summary>
39	/// Gets a value indicating whether the scope has been initialized.
40	/// </summary>
41	public bool IsScopeCreated => initializer == null;	30✔
42
43	/// <summary>
44	/// Gets the scope if it has been initialized, else default.
45	/// </summary>
46	public Scoped<V> ScopeIfCreated
47	{
48	get
49	{	33✔
50	if (initializer != null)	33✔
51	{	3✔
52	return default;	3✔
53	}
54
55	return scope;	30✔
56	}	33✔
57	}
58
59	/// <summary>
60	/// Attempts to create a lifetime for the scoped value. The lifetime guarantees the value is alive until
61	/// the lifetime is disposed.
62	/// </summary>
63	/// <param name="lifetime">When this method returns, contains the Lifetime that was created, or the default value of the type if the operation failed.</param>
64	/// <returns>true if the Lifetime was created; otherwise false.</returns>
65	public bool TryCreateLifetime(out Lifetime<V> lifetime)
66	{	33✔
67	if (scope?.IsDisposed ?? false \|\| initializer != null)	33✔
68	{	6✔
69	lifetime = default;	6✔
70	return false;	6✔
71	}
72
73	return scope.TryCreateLifetime(out lifetime);	27✔
74	}	33✔
75
76	/// <summary>
77	/// Attempts to create a lifetime for the scoped value. The lifetime guarantees the value is alive until
78	/// the lifetime is disposed.
79	/// </summary>
80	/// <param name="key">The key associated with the scoped value.</param>
81	/// <param name="valueFactory">The value factory to use to create the scoped value when it is not initialized.</param>
82	/// <returns>true if the Lifetime was created; otherwise false. If the lifetime was created, the new lifetime is also returned.</returns>
83	// backcompat: remove
84	public ValueTask<(bool success, Lifetime<V> lifetime)> TryCreateLifetimeAsync(K key, Func<K, Task<Scoped<V>>> valueFactory)
85	{	24,603✔
86	return TryCreateLifetimeAsync(key, new AsyncValueFactory<K, Scoped<V>>(valueFactory));	24,603✔
87	}	24,603✔
88
89	/// <summary>
90	/// Attempts to create a lifetime for the scoped value. The lifetime guarantees the value is alive until
91	/// the lifetime is disposed.
92	/// </summary>
93	/// <typeparam name="TFactory">The type of the value factory.</typeparam>
94	/// <param name="key">The key associated with the scoped value.</param>
95	/// <param name="valueFactory">The value factory to use to create the scoped value when it is not initialized.</param>
96	/// <returns>true if the Lifetime was created; otherwise false. If the lifetime was created, the new lifetime is also returned.</returns>
97	public async ValueTask<(bool success, Lifetime<V> lifetime)> TryCreateLifetimeAsync<TFactory>(K key, TFactory valueFactory) where TFactory : struct, IAsyncValueFactory<K, Scoped<V>>
98	{	24,822✔
99	// if disposed, return
100	if (scope?.IsDisposed ?? false)	24,822✔
101	{	198✔
102	return (false, default);	198✔
103	}
104
105	// Create scope EXACTLY once, ref count cas operates over same scope
106	if (initializer != null)	24,624✔
107	{	16,482✔
108	await InitializeScopeAsync(key, valueFactory).ConfigureAwait(false);	16,482✔
109	}	16,470✔
110
111	bool res = scope.TryCreateLifetime(out var lifetime);	24,612✔
112	return (res, lifetime);	24,612✔
113	}	24,810✔
114
115	private async ValueTask InitializeScopeAsync<TFactory>(K key, TFactory valueFactory) where TFactory : struct, IAsyncValueFactory<K, Scoped<V>>
116	{	16,482✔
117	var init = Volatile.Read(ref initializer);	16,482✔
118
119	if (init != null)	16,482✔
120	{	16,378✔
121	scope = await init.CreateScopeAsync(key, valueFactory).ConfigureAwait(false);	16,378✔
122	Volatile.Write(ref initializer, null);	16,366✔
123	}	16,366✔
124	}	16,470✔
125
126	/// <summary>
127	/// Terminates the scope and disposes the value. Once the scope is terminated, it is no longer
128	/// possible to create new lifetimes for the value.
129	/// </summary>
130	public void Dispose()
131	{	9,252✔
132	var init = initializer;	9,252✔
133
134	if (init != null && init.TryGetScope(out var disposeScope))	9,252!
UNCOV 135	{	×
UNCOV 136	scope = disposeScope;	×
UNCOV 137	}	×
138
139	// It is possible that a task was running to create the scope, but it didn't complete yet
140	// in that case this.scope == null. Initializer is now marked for dispose, and the new
141	// scope will be disposed when the task completes.
142	scope?.Dispose();	9,252✔
143	}	9,252✔
144
145	private class Initializer
146	{
147	private bool isTaskInitialized;
148	private bool isTaskCompleted;
149	private bool isDisposeRequested;
150	private Task<Scoped<V>> task;
151
152	public async ValueTask<Scoped<V>> CreateScopeAsync<TFactory>(K key, TFactory valueFactory) where TFactory : struct, IAsyncValueFactory<K, Scoped<V>>
153	{	16,378✔
154	var tcs = new TaskCompletionSource<Scoped<V>>(TaskCreationOptions.RunContinuationsAsynchronously);	16,378✔
155
156	var synchronizedTask = DoubleCheck(tcs.Task);	16,378✔
157
158	if (ReferenceEquals(synchronizedTask, tcs.Task))	16,378✔
159	{	15,393✔
160	try
161	{	15,393✔
162	var scope = await valueFactory.CreateAsync(key).ConfigureAwait(false);	15,393✔
163	tcs.SetResult(scope);	15,381✔
164
165	Volatile.Write(ref isTaskCompleted, true);	15,381✔
166
167	if (Volatile.Read(ref isDisposeRequested))	15,381✔
168	{	9✔
169	scope.Dispose();	9✔
170	}	9✔
171
172	return scope;	15,381✔
173	}
174	catch (Exception ex)	12✔
175	{	12✔
176	Volatile.Write(ref isTaskInitialized, false);	12✔
177	tcs.SetException(ex);	12✔
178	throw;	12✔
179	}
180	}
181
182	return await synchronizedTask.ConfigureAwait(false);	985✔
183	}	16,366✔
184
185	#pragma warning disable CA2002 // Do not lock on objects with weak identity
186	private Task<Scoped<V>> DoubleCheck(Task<Scoped<V>> value)
187	{	16,378✔
188	// Fast path
189	if (Volatile.Read(ref isTaskInitialized))	16,378✔
190	{	945✔
191	return task;	945✔
192	}
193
194	lock (this)	15,433✔
195	{	15,433✔
196	if (!isTaskInitialized)	15,433✔
197	{	15,393✔
198	task = value;	15,393✔
199	isTaskInitialized = true;	15,393✔
200	}	15,393✔
201	}	15,433✔
202
203	return task;	15,433✔
204	}	16,378✔
205	#pragma warning restore CA2002 // Do not lock on objects with weak identity
206
207	// <remarks>
208	// Let's say there are 2 threads, A and B:
209	// A is the init thread
210	// 1. mark isTaskInitialized = true
211	// 2. read is dispose requested
212	// B is the dispose thread
213	// 1. mark dispose requested = true
214	// 2. read isTaskInitialized
215	// Due to the rules of volatile, these reads and writes cannot be reordered.
216	// Therefore, the dispose race reduces to two possible scenarios:
217	// 1. If init task is completed, we can return it, then dispose it
218	// 2. If it is not yet completed, it is guaranteed to dispose on completion because volatile writes cannot be re-ordered.
219	// If the value factory continuously throws, the object will be neither created nor disposed. This is considered benign.
220	// </remarks>
221	public bool TryGetScope(out Scoped<V> scope)
222	{	9✔
223	Volatile.Write(ref this.isDisposeRequested, true);	9✔
224
225	if (Volatile.Read(ref isTaskCompleted))	9!
UNCOV 226	{	×
227	// isTaskCompleted is only set when there is no exception, so this is safe to return
UNCOV 228	scope = task.Result;	×
UNCOV 229	return true;	×
230	}
231
232	scope = default;	9✔
233	return false;	9✔
234	}	9✔
235	}
236	}
237	}

bitfaster / BitFaster.Caching / 6779506517

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous