summaryrefslogtreecommitdiff
path: root/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
diff options
context:
space:
mode:
Diffstat (limited to 'src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs')
-rw-r--r--src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs905
1 files changed, 505 insertions, 400 deletions
diff --git a/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs b/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
index 21d677241d..74559673bb 100644
--- a/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
+++ b/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
@@ -60,31 +60,29 @@
** may be delayed until appdomain shutdown.
===========================================================*/
+using System.Collections.Generic;
+using System.Runtime.InteropServices;
+using System.Threading;
+
namespace System.Runtime.CompilerServices
{
- using System;
- using System.Collections.Generic;
- using System.Runtime.Versioning;
- using System.Runtime.InteropServices;
-
-
#region ConditionalWeakTable
- [System.Runtime.InteropServices.ComVisible(false)]
+ [ComVisible(false)]
public sealed class ConditionalWeakTable<TKey, TValue>
where TKey : class
where TValue : class
{
+ #region Fields
+ private const int InitialCapacity = 8; // Initial length of the table. Must be a power of two.
+ private readonly object _lock; // This lock protects all mutation of data in the table. Readers do not take this lock.
+ private volatile Container _container; // The actual storage for the table; swapped out as the table grows.
+ #endregion
#region Constructors
- [System.Security.SecuritySafeCritical]
public ConditionalWeakTable()
{
- _buckets = Array.Empty<int>();
- _entries = Array.Empty<Entry>();
- _freeList = -1;
- _lock = new Object();
-
- Resize(); // Resize at once (so won't need "if initialized" checks all over)
+ _lock = new object();
+ _container = new Container(this);
}
#endregion
@@ -99,18 +97,14 @@ namespace System.Runtime.CompilerServices
// Note: The key may get garbaged collected during the TryGetValue operation. If so, TryGetValue
// may at its discretion, return "false" and set "value" to the default (as if the key was not present.)
//--------------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
public bool TryGetValue(TKey key, out TValue value)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
- lock(_lock)
- {
- VerifyIntegrity();
- return TryGetValueWorker(key, out value);
- }
+
+ return _container.TryGetValueWorker(key, out value);
}
//--------------------------------------------------------------------------------------------
@@ -123,7 +117,6 @@ namespace System.Runtime.CompilerServices
// has the right to consider any prior entries successfully removed and add a new entry without
// throwing an exception.
//--------------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
public void Add(TKey key, TValue value)
{
if (key == null)
@@ -131,22 +124,48 @@ namespace System.Runtime.CompilerServices
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
- lock(_lock)
+ lock (_lock)
{
- VerifyIntegrity();
- _invalid = true;
-
- int entryIndex = FindEntry(key);
+ object otherValue;
+ int entryIndex = _container.FindEntry(key, out otherValue);
if (entryIndex != -1)
{
- _invalid = false;
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
}
CreateEntry(key, value);
- _invalid = false;
}
+ }
+
+ //--------------------------------------------------------------------------------------------
+ // key: key to add or update. May not be null.
+ // value: value to associate with key.
+ //
+ // If the key is already entered into the dictionary, this method will update the value associated with key.
+ //--------------------------------------------------------------------------------------------
+ public void AddOrUpdate(TKey key, TValue value)
+ {
+ if (key == null)
+ {
+ ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
+ }
+
+ lock (_lock)
+ {
+ object otherValue;
+ int entryIndex = _container.FindEntry(key, out otherValue);
+
+ // if we found a key we should just update, if no we should create a new entry.
+ if (entryIndex != -1)
+ {
+ _container.UpdateValue(entryIndex, value);
+ }
+ else
+ {
+ CreateEntry(key, value);
+ }
+ }
}
//--------------------------------------------------------------------------------------------
@@ -156,9 +175,8 @@ namespace System.Runtime.CompilerServices
//
// Note: The key may get garbage collected during the Remove() operation. If so,
// Remove() will not fail or throw, however, the return value can be either true or false
- // depending on the race condition.
+ // depending on who wins the race.
//--------------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
public bool Remove(TKey key)
{
if (key == null)
@@ -166,40 +184,9 @@ namespace System.Runtime.CompilerServices
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
- lock(_lock)
+ lock (_lock)
{
- VerifyIntegrity();
- _invalid = true;
-
- int hashCode = RuntimeHelpers.GetHashCode(key) & Int32.MaxValue;
- int bucket = hashCode % _buckets.Length;
- int last = -1;
- for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
- {
- if (_entries[entriesIndex].hashCode == hashCode && _entries[entriesIndex].depHnd.GetPrimary() == key)
- {
- if (last == -1)
- {
- _buckets[bucket] = _entries[entriesIndex].next;
- }
- else
- {
- _entries[last].next = _entries[entriesIndex].next;
- }
-
- _entries[entriesIndex].depHnd.Free();
- _entries[entriesIndex].next = _freeList;
-
- _freeList = entriesIndex;
-
- _invalid = false;
- return true;
-
- }
- last = entriesIndex;
- }
- _invalid = false;
- return false;
+ return _container.Remove(key);
}
}
@@ -219,46 +206,39 @@ namespace System.Runtime.CompilerServices
// This rule permits the table to invoke createValueCallback outside the internal table lock
// to prevent deadlocks.
//--------------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
public TValue GetValue(TKey key, CreateValueCallback createValueCallback)
{
- // Our call to TryGetValue() validates key so no need for us to.
- //
- // if (key == null)
- // {
- // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
- // }
+ // key is validated by TryGetValue
if (createValueCallback == null)
{
- throw new ArgumentNullException("createValueCallback");
+ throw new ArgumentNullException(nameof(createValueCallback));
}
TValue existingValue;
- if (TryGetValue(key, out existingValue))
- {
- return existingValue;
- }
+ return TryGetValue(key, out existingValue) ?
+ existingValue :
+ GetValueLocked(key, createValueCallback);
+ }
- // If we got here, the key is not currently in table. Invoke the callback (outside the lock)
+ private TValue GetValueLocked(TKey key, CreateValueCallback createValueCallback)
+ {
+ // If we got here, the key was not in the table. Invoke the callback (outside the lock)
// to generate the new value for the key.
TValue newValue = createValueCallback(key);
- lock(_lock)
+ lock (_lock)
{
- VerifyIntegrity();
- _invalid = true;
-
- // Now that we've retaken the lock, must recheck in case there was a race condition to add the key.
- if (TryGetValueWorker(key, out existingValue))
+ // Now that we've taken the lock, must recheck in case we lost a race to add the key.
+ TValue existingValue;
+ if (_container.TryGetValueWorker(key, out existingValue))
{
- _invalid = false;
return existingValue;
}
else
{
+ // Verified in-lock that we won the race to add the key. Add it now.
CreateEntry(key, newValue);
- _invalid = false;
return newValue;
}
}
@@ -271,17 +251,15 @@ namespace System.Runtime.CompilerServices
// to create new instances as needed. If TValue does not have a default constructor, this will
// throw.
//--------------------------------------------------------------------------------------------
- public TValue GetOrCreateValue(TKey key)
- {
- return GetValue(key, k => Activator.CreateInstance<TValue>());
- }
+
+ public TValue GetOrCreateValue(TKey key) => GetValue(key, _ => Activator.CreateInstance<TValue>());
public delegate TValue CreateValueCallback(TKey key);
-
+
#endregion
- #region internal members
-
+ #region Internal members
+
//--------------------------------------------------------------------------------------------
// Find a key that equals (value equality) with the given key - don't use in perf critical path
// Note that it calls out to Object.Equals which may calls the override version of Equals
@@ -290,56 +268,26 @@ namespace System.Runtime.CompilerServices
// if you know for sure that either you won't run into dead locks or you need to live with the
// possiblity
//--------------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
[FriendAccessAllowed]
internal TKey FindEquivalentKeyUnsafe(TKey key, out TValue value)
{
lock (_lock)
{
- for (int bucket = 0; bucket < _buckets.Length; ++bucket)
- {
- for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
- {
- object thisKey, thisValue;
- _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out thisKey, out thisValue);
- if (Object.Equals(thisKey, key))
- {
- value = (TValue) thisValue;
- return (TKey) thisKey;
- }
- }
- }
+ return _container.FindEquivalentKeyUnsafe(key, out value);
}
-
- value = default(TValue);
- return null;
}
-
+
//--------------------------------------------------------------------------------------------
// Returns a collection of keys - don't use in perf critical path
//--------------------------------------------------------------------------------------------
internal ICollection<TKey> Keys
{
- [System.Security.SecuritySafeCritical]
get
{
- List<TKey> list = new List<TKey>();
lock (_lock)
{
- for (int bucket = 0; bucket < _buckets.Length; ++bucket)
- {
- for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
- {
- TKey thisKey = (TKey) _entries[entriesIndex].depHnd.GetPrimary();
- if (thisKey != null)
- {
- list.Add(thisKey);
- }
- }
- }
+ return _container.Keys;
}
-
- return list;
}
}
@@ -348,332 +296,500 @@ namespace System.Runtime.CompilerServices
//--------------------------------------------------------------------------------------------
internal ICollection<TValue> Values
{
- [System.Security.SecuritySafeCritical]
get
{
- List<TValue> list = new List<TValue>();
lock (_lock)
{
- for (int bucket = 0; bucket < _buckets.Length; ++bucket)
- {
- for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
- {
- Object primary = null;
- Object secondary = null;
-
- _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out primary, out secondary);
-
- // Now that we've secured a strong reference to the secondary, must check the primary again
- // to ensure it didn't expire (otherwise, we open a race condition where TryGetValue misreports an
- // expired key as a live key with a null value.)
- if (primary != null)
- {
- list.Add((TValue)secondary);
- }
- }
- }
+ return _container.Values;
}
-
- return list;
}
}
-
+
//--------------------------------------------------------------------------------------------
// Clear all the key/value pairs
//--------------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
internal void Clear()
{
lock (_lock)
{
- // Clear the buckets
- for (int bucketIndex = 0; bucketIndex < _buckets.Length; bucketIndex++)
- {
- _buckets[bucketIndex] = -1;
- }
-
- // Clear the entries and link them backwards together as part of free list
- int entriesIndex;
- for (entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
- {
- if (_entries[entriesIndex].depHnd.IsAllocated)
- {
- _entries[entriesIndex].depHnd.Free();
- }
-
- // Link back wards as free list
- _entries[entriesIndex].next = entriesIndex - 1;
- }
-
- _freeList = entriesIndex - 1;
- }
+ _container = new Container(this);
+ }
}
#endregion
-
+
#region Private Members
- [System.Security.SecurityCritical]
+
//----------------------------------------------------------------------------------------
- // Worker for finding a key/value pair
+ // Worker for adding a new key/value pair.
+ // Will resize the container if it is full
//
// Preconditions:
// Must hold _lock.
- // Key already validated as non-null
+ // Key already validated as non-null and not already in table.
//----------------------------------------------------------------------------------------
- private bool TryGetValueWorker(TKey key, out TValue value)
+ private void CreateEntry(TKey key, TValue value)
{
- int entryIndex = FindEntry(key);
- if (entryIndex != -1)
+ Debug.Assert(Monitor.IsEntered(_lock));
+
+ Container c = _container;
+ if (!c.HasCapacity)
{
- Object primary = null;
- Object secondary = null;
- _entries[entryIndex].depHnd.GetPrimaryAndSecondary(out primary, out secondary);
- // Now that we've secured a strong reference to the secondary, must check the primary again
- // to ensure it didn't expire (otherwise, we open a race condition where TryGetValue misreports an
- // expired key as a live key with a null value.)
- if (primary != null)
- {
- value = (TValue)secondary;
- return true;
- }
+ _container = c = c.Resize();
}
+ c.CreateEntryNoResize(key, value);
+ }
+
+ private static bool IsPowerOfTwo(int value) => (value > 0) && ((value & (value - 1)) == 0);
- value = default(TValue);
- return false;
+ #endregion
+
+ #region Private Data Members
+ //--------------------------------------------------------------------------------------------
+ // Entry can be in one of four states:
+ //
+ // - Unused (stored with an index _firstFreeEntry and above)
+ // depHnd.IsAllocated == false
+ // hashCode == <dontcare>
+ // next == <dontcare>)
+ //
+ // - Used with live key (linked into a bucket list where _buckets[hashCode & (_buckets.Length - 1)] points to first entry)
+ // depHnd.IsAllocated == true, depHnd.GetPrimary() != null
+ // hashCode == RuntimeHelpers.GetHashCode(depHnd.GetPrimary()) & Int32.MaxValue
+ // next links to next Entry in bucket.
+ //
+ // - Used with dead key (linked into a bucket list where _buckets[hashCode & (_buckets.Length - 1)] points to first entry)
+ // depHnd.IsAllocated == true, depHnd.GetPrimary() == null
+ // hashCode == <notcare>
+ // next links to next Entry in bucket.
+ //
+ // - Has been removed from the table (by a call to Remove)
+ // depHnd.IsAllocated == true, depHnd.GetPrimary() == <notcare>
+ // hashCode == -1
+ // next links to next Entry in bucket.
+ //
+ // The only difference between "used with live key" and "used with dead key" is that
+ // depHnd.GetPrimary() returns null. The transition from "used with live key" to "used with dead key"
+ // happens asynchronously as a result of normal garbage collection. The dictionary itself
+ // receives no notification when this happens.
+ //
+ // When the dictionary grows the _entries table, it scours it for expired keys and does not
+ // add those to the new container.
+ //--------------------------------------------------------------------------------------------
+ private struct Entry
+ {
+ public DependentHandle depHnd; // Holds key and value using a weak reference for the key and a strong reference
+ // for the value that is traversed only if the key is reachable without going through the value.
+ public int HashCode; // Cached copy of key's hashcode
+ public int Next; // Index of next entry, -1 if last
}
- //----------------------------------------------------------------------------------------
- // Worker for adding a new key/value pair.
//
- // Preconditions:
- // Must hold _lock.
- // Key already validated as non-null and not already in table.
- //----------------------------------------------------------------------------------------
- [System.Security.SecurityCritical]
- private void CreateEntry(TKey key, TValue value)
+ // Container holds the actual data for the table. A given instance of Container always has the same capacity. When we need
+ // more capacity, we create a new Container, copy the old one into the new one, and discard the old one. This helps enable lock-free
+ // reads from the table, as readers never need to deal with motion of entries due to rehashing.
+ //
+ private sealed class Container
{
- if (_freeList == -1)
+ private readonly ConditionalWeakTable<TKey, TValue> _parent; // the ConditionalWeakTable with which this container is associated
+ private int[] _buckets; // _buckets[hashcode & (_buckets.Length - 1)] contains index of the first entry in bucket (-1 if empty)
+ private Entry[] _entries; // the table entries containing the stored dependency handles
+ private int _firstFreeEntry; // _firstFreeEntry < _entries.Length => table has capacity, entries grow from the bottom of the table.
+ private bool _invalid; // flag detects if OOM or other background exception threw us out of the lock.
+ private bool _finalized; // set to true when initially finalized
+ private volatile object _oldKeepAlive; // used to ensure the next allocated container isn't finalized until this one is GC'd
+
+ internal Container(ConditionalWeakTable<TKey, TValue> parent)
{
- Resize();
+ Debug.Assert(parent != null);
+ Debug.Assert(IsPowerOfTwo(InitialCapacity));
+
+ int size = InitialCapacity;
+ _buckets = new int[size];
+ for (int i = 0; i < _buckets.Length; i++)
+ {
+ _buckets[i] = -1;
+ }
+ _entries = new Entry[size];
+
+ // Only store the parent after all of the allocations have happened successfully.
+ // Otherwise, as part of growing or clearing the container, we could end up allocating
+ // a new Container that fails (OOMs) part way through construction but that gets finalized
+ // and ends up clearing out some other container present in the associated CWT.
+ _parent = parent;
}
- int hashCode = RuntimeHelpers.GetHashCode(key) & Int32.MaxValue;
- int bucket = hashCode % _buckets.Length;
+ private Container(ConditionalWeakTable<TKey, TValue> parent, int[] buckets, Entry[] entries, int firstFreeEntry)
+ {
+ Debug.Assert(parent != null);
+ Debug.Assert(buckets != null);
+ Debug.Assert(entries != null);
+ Debug.Assert(buckets.Length == entries.Length);
+ Debug.Assert(IsPowerOfTwo(buckets.Length));
+
+ _parent = parent;
+ _buckets = buckets;
+ _entries = entries;
+ _firstFreeEntry = firstFreeEntry;
+ }
- int newEntry = _freeList;
- _freeList = _entries[newEntry].next;
+ internal bool HasCapacity => _firstFreeEntry < _entries.Length;
- _entries[newEntry].hashCode = hashCode;
- _entries[newEntry].depHnd = new DependentHandle(key, value);
- _entries[newEntry].next = _buckets[bucket];
+ //----------------------------------------------------------------------------------------
+ // Worker for adding a new key/value pair.
+ // Preconditions:
+ // Container must NOT be full
+ //----------------------------------------------------------------------------------------
+ internal void CreateEntryNoResize(TKey key, TValue value)
+ {
+ Debug.Assert(HasCapacity);
- _buckets[bucket] = newEntry;
+ VerifyIntegrity();
+ _invalid = true;
- }
+ int hashCode = RuntimeHelpers.GetHashCode(key) & int.MaxValue;
+ int newEntry = _firstFreeEntry++;
- //----------------------------------------------------------------------------------------
- // This does two things: resize and scrub expired keys off bucket lists.
- //
- // Precondition:
- // Must hold _lock.
- //
- // Postcondition:
- // _freeList is non-empty on exit.
- //----------------------------------------------------------------------------------------
- [System.Security.SecurityCritical]
- private void Resize()
- {
- // Start by assuming we won't resize.
- int newSize = _buckets.Length;
+ _entries[newEntry].HashCode = hashCode;
+ _entries[newEntry].depHnd = new DependentHandle(key, value);
+ int bucket = hashCode & (_buckets.Length - 1);
+ _entries[newEntry].Next = _buckets[bucket];
+
+ // This write must be volatile, as we may be racing with concurrent readers. If they see
+ // the new entry, they must also see all of the writes earlier in this method.
+ Volatile.Write(ref _buckets[bucket], newEntry);
+
+ _invalid = false;
+ }
- // If any expired keys exist, we won't resize.
- bool hasExpiredEntries = false;
- int entriesIndex;
- for (entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
+ //----------------------------------------------------------------------------------------
+ // Worker for finding a key/value pair
+ //
+ // Preconditions:
+ // Must hold _lock.
+ // Key already validated as non-null
+ //----------------------------------------------------------------------------------------
+ internal bool TryGetValueWorker(TKey key, out TValue value)
{
- if ( _entries[entriesIndex].depHnd.IsAllocated && _entries[entriesIndex].depHnd.GetPrimary() == null)
+ object secondary;
+ int entryIndex = FindEntry(key, out secondary);
+ value = JitHelpers.UnsafeCast<TValue>(secondary);
+ return entryIndex != -1;
+ }
+
+ //----------------------------------------------------------------------------------------
+ // Returns -1 if not found (if key expires during FindEntry, this can be treated as "not found.")
+ //
+ // Preconditions:
+ // Must hold _lock, or be prepared to retry the search while holding _lock.
+ // Key already validated as non-null.
+ //----------------------------------------------------------------------------------------
+ internal int FindEntry(TKey key, out object value)
+ {
+ int hashCode = RuntimeHelpers.GetHashCode(key) & int.MaxValue;
+ int bucket = hashCode & (_buckets.Length - 1);
+ for (int entriesIndex = Volatile.Read(ref _buckets[bucket]); entriesIndex != -1; entriesIndex = _entries[entriesIndex].Next)
{
- hasExpiredEntries = true;
- break;
+ if (_entries[entriesIndex].HashCode == hashCode)
+ {
+ object primary, secondary;
+ _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out primary, out secondary);
+ if (primary == key)
+ {
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+ value = secondary;
+ return entriesIndex;
+ }
+ }
}
+
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+ value = null;
+ return -1;
}
- if (!hasExpiredEntries)
+ internal bool Remove(TKey key)
{
- newSize = System.Collections.HashHelpers.GetPrime(_buckets.Length == 0 ? _initialCapacity + 1 : _buckets.Length * 2);
+ VerifyIntegrity();
+
+ object value;
+ int entryIndex = FindEntry(key, out value);
+ if (entryIndex != -1)
+ {
+ ref Entry entry = ref _entries[entryIndex];
+
+ // We do not free the handle here, as we may be racing with readers who already saw the hash code.
+ // Instead, we simply overwrite the entry's hash code, so subsequent reads will ignore it.
+ // The handle will be free'd in Container's finalizer, after the table is resized or discarded.
+ Volatile.Write(ref entry.HashCode, -1);
+
+ // Also, clear the key to allow GC to collect objects pointed to by the entry
+ entry.depHnd.SetPrimary(null);
+
+ return true;
+ }
+
+ return false;
}
- // Reallocate both buckets and entries and rebuild the bucket and freelists from scratch.
- // This serves both to scrub entries with expired keys and to put the new entries in the proper bucket.
- int newFreeList = -1;
- int[] newBuckets = new int[newSize];
- for (int bucketIndex = 0; bucketIndex < newSize; bucketIndex++)
+ internal void UpdateValue(int entryIndex, TValue newValue)
{
- newBuckets[bucketIndex] = -1;
+ Debug.Assert(entryIndex != -1);
+
+ VerifyIntegrity();
+ _invalid = true;
+
+ _entries[entryIndex].depHnd.SetSecondary(newValue);
+
+ _invalid = false;
}
- Entry[] newEntries = new Entry[newSize];
- // Migrate existing entries to the new table.
- for (entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
+ //----------------------------------------------------------------------------------------
+ // This does two things: resize and scrub expired keys off bucket lists.
+ //
+ // Precondition:
+ // Must hold _lock.
+ //
+ // Postcondition:
+ // _firstEntry is less than _entries.Length on exit, that is, the table has at least one free entry.
+ //----------------------------------------------------------------------------------------
+ internal Container Resize()
{
- DependentHandle depHnd = _entries[entriesIndex].depHnd;
- if (depHnd.IsAllocated && depHnd.GetPrimary() != null)
+ // Start by assuming we won't resize.
+ int newSize = _buckets.Length;
+
+ // If any expired or removed keys exist, we won't resize.
+ bool hasExpiredEntries = false;
+ for (int entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
{
- // Entry is used and has not expired. Link it into the appropriate bucket list.
- int bucket = _entries[entriesIndex].hashCode % newSize;
- newEntries[entriesIndex].depHnd = depHnd;
- newEntries[entriesIndex].hashCode = _entries[entriesIndex].hashCode;
- newEntries[entriesIndex].next = newBuckets[bucket];
- newBuckets[bucket] = entriesIndex;
+ if (_entries[entriesIndex].HashCode == -1)
+ {
+ // the entry was removed
+ hasExpiredEntries = true;
+ break;
+ }
+
+ if (_entries[entriesIndex].depHnd.IsAllocated && _entries[entriesIndex].depHnd.GetPrimary() == null)
+ {
+ // the entry has expired
+ hasExpiredEntries = true;
+ break;
+ }
}
- else
+
+ if (!hasExpiredEntries)
{
- // Entry has either expired or was on the freelist to begin with. Either way
- // insert it on the new freelist.
- _entries[entriesIndex].depHnd.Free();
- newEntries[entriesIndex].depHnd = new DependentHandle();
- newEntries[entriesIndex].next = newFreeList;
- newFreeList = entriesIndex;
+ // Not necessary to check for overflow here, the attempt to allocate new arrays will throw
+ newSize = _buckets.Length * 2;
}
+
+ return Resize(newSize);
}
- // Add remaining entries to freelist.
- while (entriesIndex != newEntries.Length)
+ internal Container Resize(int newSize)
{
- newEntries[entriesIndex].depHnd = new DependentHandle();
- newEntries[entriesIndex].next = newFreeList;
- newFreeList = entriesIndex;
- entriesIndex++;
- }
+ Debug.Assert(IsPowerOfTwo(newSize));
- _buckets = newBuckets;
- _entries = newEntries;
- _freeList = newFreeList;
- }
+ // Reallocate both buckets and entries and rebuild the bucket and entries from scratch.
+ // This serves both to scrub entries with expired keys and to put the new entries in the proper bucket.
+ int[] newBuckets = new int[newSize];
+ for (int bucketIndex = 0; bucketIndex < newSize; bucketIndex++)
+ {
+ newBuckets[bucketIndex] = -1;
+ }
+ Entry[] newEntries = new Entry[newSize];
+ int newEntriesIndex = 0;
- //----------------------------------------------------------------------------------------
- // Returns -1 if not found (if key expires during FindEntry, this can be treated as "not found.")
- //
- // Preconditions:
- // Must hold _lock.
- // Key already validated as non-null.
- //----------------------------------------------------------------------------------------
- [System.Security.SecurityCritical]
- private int FindEntry(TKey key)
- {
- int hashCode = RuntimeHelpers.GetHashCode(key) & Int32.MaxValue;
- for (int entriesIndex = _buckets[hashCode % _buckets.Length]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].next)
+ // Migrate existing entries to the new table.
+ for (int entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
+ {
+ int hashCode = _entries[entriesIndex].HashCode;
+ DependentHandle depHnd = _entries[entriesIndex].depHnd;
+ if (hashCode != -1 && depHnd.IsAllocated)
+ {
+ if (depHnd.GetPrimary() != null)
+ {
+ // Entry is used and has not expired. Link it into the appropriate bucket list.
+ newEntries[newEntriesIndex].HashCode = hashCode;
+ newEntries[newEntriesIndex].depHnd = depHnd;
+ int bucket = hashCode & (newBuckets.Length - 1);
+ newEntries[newEntriesIndex].Next = newBuckets[bucket];
+ newBuckets[bucket] = newEntriesIndex;
+ newEntriesIndex++;
+ }
+ else
+ {
+ // Pretend the item was removed, so that this container's finalizer
+ // will clean up this dependent handle.
+ Volatile.Write(ref _entries[entriesIndex].HashCode, -1);
+ }
+ }
+ }
+
+ // Create the new container. We want to transfer the responsibility of freeing the handles from
+ // the old container to the new container, and also ensure that the new container isn't finalized
+ // while the old container may still be in use. As such, we store a reference from the old container
+ // to the new one, which will keep the new container alive as long as the old one is.
+ var newContainer = new Container(_parent, newBuckets, newEntries, newEntriesIndex);
+ _oldKeepAlive = newContainer; // once this is set, the old container's finalizer will not free transferred dependent handles
+
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+
+ return newContainer;
+ }
+
+ internal ICollection<TKey> Keys
{
- if (_entries[entriesIndex].hashCode == hashCode && _entries[entriesIndex].depHnd.GetPrimary() == key)
+ get
{
- return entriesIndex;
+ var list = new List<TKey>();
+
+ for (int bucket = 0; bucket < _buckets.Length; ++bucket)
+ {
+ for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].Next)
+ {
+ TKey thisKey = JitHelpers.UnsafeCast<TKey>(_entries[entriesIndex].depHnd.GetPrimary());
+ if (thisKey != null)
+ {
+ list.Add(thisKey);
+ }
+ }
+ }
+
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+ return list;
}
}
- return -1;
- }
- //----------------------------------------------------------------------------------------
- // Precondition:
- // Must hold _lock.
- //----------------------------------------------------------------------------------------
- private void VerifyIntegrity()
- {
- if (_invalid)
+ internal ICollection<TValue> Values
{
- throw new InvalidOperationException(Environment.GetResourceString("CollectionCorrupted"));
+ get
+ {
+ var list = new List<TValue>();
+
+ for (int bucket = 0; bucket < _buckets.Length; ++bucket)
+ {
+ for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].Next)
+ {
+ object primary = null, secondary = null;
+ _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out primary, out secondary);
+
+ // Now that we've secured a strong reference to the secondary, must check the primary again
+ // to ensure it didn't expire (otherwise, we open a race where TryGetValue misreports an
+ // expired key as a live key with a null value.)
+ if (primary != null)
+ {
+ list.Add(JitHelpers.UnsafeCast<TValue>(secondary));
+ }
+ }
+ }
+
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+ return list;
+ }
}
- }
- //----------------------------------------------------------------------------------------
- // Finalizer.
- //----------------------------------------------------------------------------------------
- [System.Security.SecuritySafeCritical]
- ~ConditionalWeakTable()
- {
+ internal TKey FindEquivalentKeyUnsafe(TKey key, out TValue value)
+ {
+ for (int bucket = 0; bucket < _buckets.Length; ++bucket)
+ {
+ for (int entriesIndex = _buckets[bucket]; entriesIndex != -1; entriesIndex = _entries[entriesIndex].Next)
+ {
+ if (_entries[entriesIndex].HashCode == -1)
+ {
+ continue; // removed entry whose handle is awaiting condemnation by the finalizer.
+ }
- // We're just freeing per-appdomain unmanaged handles here. If we're already shutting down the AD,
- // don't bother.
- //
- // (Despite its name, Environment.HasShutdownStart also returns true if the current AD is finalizing.)
- if (Environment.HasShutdownStarted)
+ object thisKey, thisValue;
+ _entries[entriesIndex].depHnd.GetPrimaryAndSecondary(out thisKey, out thisValue);
+ if (Equals(thisKey, key))
+ {
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+ value = JitHelpers.UnsafeCast<TValue>(thisValue);
+ return JitHelpers.UnsafeCast<TKey>(thisKey);
+ }
+ }
+ }
+
+ GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+ value = default(TValue);
+ return null;
+ }
+
+ //----------------------------------------------------------------------------------------
+ // Precondition:
+ // Must hold _lock.
+ //----------------------------------------------------------------------------------------
+ private void VerifyIntegrity()
{
- return;
+ if (_invalid)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("CollectionCorrupted"));
+ }
}
- if (_lock != null)
+ //----------------------------------------------------------------------------------------
+ // Finalizer.
+ //----------------------------------------------------------------------------------------
+ ~Container()
{
- lock(_lock)
+ // We're just freeing per-appdomain unmanaged handles here. If we're already shutting down the AD,
+ // don't bother. (Despite its name, Environment.HasShutdownStart also returns true if the current
+ // AD is finalizing.) We also skip doing anything if the container is invalid, including if someone
+ // the container object was allocated but its associated table never set.
+ if (Environment.HasShutdownStarted || _invalid || _parent == null)
{
- if (_invalid)
+ return;
+ }
+
+ // It's possible that the ConditionalWeakTable could have been resurrected, in which case code could
+ // be accessing this Container as it's being finalized. We don't support usage after finalization,
+ // but we also don't want to potentially corrupt state by allowing dependency handles to be used as
+ // or after they've been freed. To avoid that, if it's at all possible that another thread has a
+ // reference to this container via the CWT, we remove such a reference and then re-register for
+ // finalization: the next time around, we can be sure that no references remain to this and we can
+ // clean up the dependency handles without fear of corruption.
+ if (!_finalized)
+ {
+ _finalized = true;
+ lock (_parent._lock)
{
- return;
+ if (_parent._container == this)
+ {
+ _parent._container = null;
+ }
}
- Entry[] entries = _entries;
+ GC.ReRegisterForFinalize(this); // next time it's finalized, we'll be sure there are no remaining refs
+ return;
+ }
- // Make sure anyone sneaking into the table post-resurrection
- // gets booted before they can damage the native handle table.
- _invalid = true;
- _entries = null;
- _buckets = null;
+ Entry[] entries = _entries;
+ _invalid = true;
+ _entries = null;
+ _buckets = null;
+ if (entries != null)
+ {
for (int entriesIndex = 0; entriesIndex < entries.Length; entriesIndex++)
{
- entries[entriesIndex].depHnd.Free();
+ // We need to free handles in two cases:
+ // - If this container still owns the dependency handle (meaning ownership hasn't been transferred
+ // to another container that replaced this one), then it should be freed.
+ // - If this container had the entry removed, then even if in general ownership was transferred to
+ // another container, removed entries are not, therefore this container must free them.
+ if (_oldKeepAlive == null || entries[entriesIndex].HashCode == -1)
+ {
+ entries[entriesIndex].depHnd.Free();
+ }
}
}
}
}
#endregion
-
- #region Private Data Members
- //--------------------------------------------------------------------------------------------
- // Entry can be in one of three states:
- //
- // - Linked into the freeList (_freeList points to first entry)
- // depHnd.IsAllocated == false
- // hashCode == <dontcare>
- // next links to next Entry on freelist)
- //
- // - Used with live key (linked into a bucket list where _buckets[hashCode % _buckets.Length] points to first entry)
- // depHnd.IsAllocated == true, depHnd.GetPrimary() != null
- // hashCode == RuntimeHelpers.GetHashCode(depHnd.GetPrimary()) & Int32.MaxValue
- // next links to next Entry in bucket.
- //
- // - Used with dead key (linked into a bucket list where _buckets[hashCode % _buckets.Length] points to first entry)
- // depHnd.IsAllocated == true, depHnd.GetPrimary() == null
- // hashCode == <notcare>
- // next links to next Entry in bucket.
- //
- // The only difference between "used with live key" and "used with dead key" is that
- // depHnd.GetPrimary() returns null. The transition from "used with live key" to "used with dead key"
- // happens asynchronously as a result of normal garbage collection. The dictionary itself
- // receives no notification when this happens.
- //
- // When the dictionary grows the _entries table, it scours it for expired keys and puts those
- // entries back on the freelist.
- //--------------------------------------------------------------------------------------------
- private struct Entry
- {
- public DependentHandle depHnd; // Holds key and value using a weak reference for the key and a strong reference
- // for the value that is traversed only if the key is reachable without going through the value.
- public int hashCode; // Cached copy of key's hashcode
- public int next; // Index of next entry, -1 if last
- }
-
- private int[] _buckets; // _buckets[hashcode & _buckets.Length] contains index of first entry in bucket (-1 if empty)
- private Entry[] _entries;
- private int _freeList; // -1 = empty, else index of first unused Entry
- private const int _initialCapacity = 5;
- private readonly Object _lock; // this could be a ReaderWriterLock but CoreCLR does not support RWLocks.
- private bool _invalid; // flag detects if OOM or other background exception threw us out of the lock.
- #endregion
}
#endregion
-
-
-
#region DependentHandle
//=========================================================================================
// This struct collects all operations on native DependentHandles. The DependentHandle
@@ -700,15 +816,10 @@ namespace System.Runtime.CompilerServices
// to use DependentHandles in a thread-safe way.
//=========================================================================================
[ComVisible(false)]
- struct DependentHandle
+ internal struct DependentHandle
{
#region Constructors
- #if FEATURE_CORECLR
- [System.Security.SecuritySafeCritical] // auto-generated
- #else
- [System.Security.SecurityCritical]
- #endif
- public DependentHandle(Object primary, Object secondary)
+ public DependentHandle(object primary, object secondary)
{
IntPtr handle = (IntPtr)0;
nInitialize(primary, secondary, out handle);
@@ -718,44 +829,37 @@ namespace System.Runtime.CompilerServices
#endregion
#region Public Members
- public bool IsAllocated
- {
- get
- {
- return _handle != (IntPtr)0;
- }
- }
+ public bool IsAllocated => _handle != IntPtr.Zero;
// Getting the secondary object is more expensive than getting the first so
// we provide a separate primary-only accessor for those times we only want the
// primary.
- #if FEATURE_CORECLR
- [System.Security.SecuritySafeCritical] // auto-generated
- #else
- [System.Security.SecurityCritical]
- #endif
- public Object GetPrimary()
+ public object GetPrimary()
{
- Object primary;
+ object primary;
nGetPrimary(_handle, out primary);
return primary;
}
- #if FEATURE_CORECLR
- [System.Security.SecuritySafeCritical] // auto-generated
- #else
- [System.Security.SecurityCritical]
- #endif
- public void GetPrimaryAndSecondary(out Object primary, out Object secondary)
+ public void GetPrimaryAndSecondary(out object primary, out object secondary)
{
nGetPrimaryAndSecondary(_handle, out primary, out secondary);
}
+ public void SetPrimary(object primary)
+ {
+ nSetPrimary(_handle, primary);
+ }
+
+ public void SetSecondary(object secondary)
+ {
+ nSetSecondary(_handle, secondary);
+ }
+
//----------------------------------------------------------------------
// Forces dependentHandle back to non-allocated state (if not already there)
// and frees the handle if needed.
//----------------------------------------------------------------------
- [System.Security.SecurityCritical]
public void Free()
{
if (_handle != (IntPtr)0)
@@ -768,20 +872,22 @@ namespace System.Runtime.CompilerServices
#endregion
#region Private Members
- [System.Security.SecurityCritical]
- [MethodImplAttribute(MethodImplOptions.InternalCall)]
- private static extern void nInitialize(Object primary, Object secondary, out IntPtr dependentHandle);
+ [MethodImpl(MethodImplOptions.InternalCall)]
+ private static extern void nInitialize(object primary, object secondary, out IntPtr dependentHandle);
+
+ [MethodImpl(MethodImplOptions.InternalCall)]
+ private static extern void nGetPrimary(IntPtr dependentHandle, out object primary);
- [System.Security.SecurityCritical]
- [MethodImplAttribute(MethodImplOptions.InternalCall)]
- private static extern void nGetPrimary(IntPtr dependentHandle, out Object primary);
+ [MethodImpl(MethodImplOptions.InternalCall)]
+ private static extern void nGetPrimaryAndSecondary(IntPtr dependentHandle, out object primary, out object secondary);
- [System.Security.SecurityCritical]
- [MethodImplAttribute(MethodImplOptions.InternalCall)]
- private static extern void nGetPrimaryAndSecondary(IntPtr dependentHandle, out Object primary, out Object secondary);
+ [MethodImpl(MethodImplOptions.InternalCall)]
+ private static extern void nSetPrimary(IntPtr dependentHandle, object primary);
- [System.Security.SecurityCritical]
- [MethodImplAttribute(MethodImplOptions.InternalCall)]
+ [MethodImpl(MethodImplOptions.InternalCall)]
+ private static extern void nSetSecondary(IntPtr dependentHandle, object secondary);
+
+ [MethodImpl(MethodImplOptions.InternalCall)]
private static extern void nFree(IntPtr dependentHandle);
#endregion
@@ -792,4 +898,3 @@ namespace System.Runtime.CompilerServices
} // struct DependentHandle
#endregion
}
-