Imported Upstream version 1.0.0.9910upstream/1.0.0.9910

1 files changed, 307 insertions, 59 deletions

diff --git a/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs b/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
index 74559673bb..4b2648ba6f 100644
--- a/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
+++ b/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs
@@ -46,7 +46,6 @@
 **    expose the full public surface area.
 **
 **
-**
 ** Thread safety guarantees:
 **
 **    ConditionalWeakTable is fully thread-safe and requires no
@@ -60,6 +59,7 @@
 **    may be delayed until appdomain shutdown.
 ===========================================================*/
 
+using System.Collections;
 using System.Collections.Generic;
 using System.Runtime.InteropServices;
 using System.Threading;
@@ -67,8 +67,7 @@ using System.Threading;
 namespace System.Runtime.CompilerServices
 {
     #region ConditionalWeakTable
-    [ComVisible(false)]
-    public sealed class ConditionalWeakTable<TKey, TValue>
+    public sealed class ConditionalWeakTable<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
         where TKey : class
         where TValue : class
     {
@@ -76,6 +75,7 @@ namespace System.Runtime.CompilerServices
         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.
+        private int _activeEnumeratorRefCount;  // The number of outstanding enumerators on the table
         #endregion
 
         #region Constructors
@@ -190,6 +190,34 @@ namespace System.Runtime.CompilerServices
             }
         }
 
+        //--------------------------------------------------------------------------------------------
+        // Clear all the key/value pairs
+        //--------------------------------------------------------------------------------------------
+        public void Clear()
+        {
+            lock (_lock)
+            {
+                // To clear, we would prefer to simply drop the existing container
+                // and replace it with an empty one, as that's overall more efficient.
+                // However, if there are any active enumerators, we don't want to do
+                // that as it will end up removing all of the existing entries and
+                // allowing new items to be added at the same indices when the container
+                // is filled and replaced, and one of the guarantees we try to make with
+                // enumeration is that new items added after enumeration starts won't be
+                // included in the enumeration. As such, if there are active enumerators,
+                // we simply use the container's removal functionality to remove all of the
+                // keys; then when the table is resized, if there are still active enumerators,
+                // these empty slots will be maintained.
+                if (_activeEnumeratorRefCount > 0)
+                {
+                    _container.RemoveAllKeys();
+                }
+                else
+                {
+                    _container = new Container(this);
+                }
+            }
+        }
 
         //--------------------------------------------------------------------------------------------
         // key:                 key of the value to find. Cannot be null.
@@ -256,6 +284,148 @@ namespace System.Runtime.CompilerServices
 
         public delegate TValue CreateValueCallback(TKey key);
 
+        //--------------------------------------------------------------------------------------------
+        // Gets an enumerator for the table.  The returned enumerator will not extend the lifetime of
+        // any object pairs in the table, other than the one that's Current.  It will not return entries
+        // that have already been collected, nor will it return entries added after the enumerator was
+        // retrieved.  It may not return all entries that were present when the enumerat was retrieved,
+        // however, such as not returning entries that were collected or removed after the enumerator
+        // was retrieved but before they were enumerated.
+        //--------------------------------------------------------------------------------------------
+        IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
+        {
+            lock (_lock)
+            {
+                Container c = _container;
+                return c == null || c.FirstFreeEntry == 0 ?
+                    ((IEnumerable<KeyValuePair<TKey, TValue>>)Array.Empty<KeyValuePair<TKey, TValue>>()).GetEnumerator() :
+                    new Enumerator(this);
+            }
+        }
+
+        IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<KeyValuePair<TKey, TValue>>)this).GetEnumerator();
+
+        /// <summary>Provides an enumerator for the table.</summary>
+        private sealed class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
+        {
+            // The enumerator would ideally hold a reference to the Container and the end index within that
+            // container.  However, the safety of the CWT depends on the only reference to the Container being
+            // from the CWT itself; the Container then employs a two-phase finalization scheme, where the first
+            // phase nulls out that parent CWT's reference, guaranteeing that the second time it's finalized there
+            // can be no other existing references to it in use that would allow for concurrent usage of the
+            // native handles with finalization.  We would break that if we allowed this Enumerator to hold a
+            // reference to the Container.  Instead, the Enumerator holds a reference to the CWT rather than to
+            // the Container, and it maintains the CWT._activeEnumeratorRefCount field to track whether there
+            // are outstanding enumerators that have yet to be disposed/finalized.  If there aren't any, the CWT
+            // behaves as it normally does.  If there are, certain operations are affected, in particular resizes.
+            // Normally when the CWT is resized, it enumerates the contents of the table looking for indices that
+            // contain entries which have been collected or removed, and it frees those up, effectively moving
+            // down all subsequent entries in the container (not in the existing container, but in a replacement).
+            // This, however, would cause the enumerator's understanding of indices to break.  So, as long as
+            // there is any outstanding enumerator, no compaction is performed.
+
+            private ConditionalWeakTable<TKey, TValue> _table; // parent table, set to null when disposed
+            private readonly int _maxIndexInclusive;           // last index in the container that should be enumerated
+            private int _currentIndex = -1;                    // the current index into the container
+            private KeyValuePair<TKey, TValue> _current;       // the current entry set by MoveNext and returned from Current
+
+            public Enumerator(ConditionalWeakTable<TKey, TValue> table)
+            {
+                Debug.Assert(table != null, "Must provide a valid table");
+                Debug.Assert(Monitor.IsEntered(table._lock), "Must hold the _lock lock to construct the enumerator");
+                Debug.Assert(table._container != null, "Should not be used on a finalized table");
+                Debug.Assert(table._container.FirstFreeEntry > 0, "Should have returned an empty enumerator instead");
+
+                // Store a reference to the parent table and increase its active enumerator count.
+                _table = table;
+                Debug.Assert(table._activeEnumeratorRefCount >= 0, "Should never have a negative ref count before incrementing");
+                table._activeEnumeratorRefCount++;
+
+                // Store the max index to be enumerated.
+                _maxIndexInclusive = table._container.FirstFreeEntry - 1;
+                _currentIndex = -1;
+            }
+
+            ~Enumerator() { Dispose(); }
+
+            public void Dispose()
+            {
+                // Use an interlocked operation to ensure that only one thread can get access to
+                // the _table for disposal and thus only decrement the ref count once.
+                ConditionalWeakTable<TKey, TValue> table = Interlocked.Exchange(ref _table, null);
+                if (table != null)
+                {
+                    // Ensure we don't keep the last current alive unnecessarily
+                    _current = default(KeyValuePair<TKey, TValue>);
+
+                    // Decrement the ref count that was incremented when constructed
+                    lock (table._lock)
+                    {
+                        table._activeEnumeratorRefCount--;
+                        Debug.Assert(table._activeEnumeratorRefCount >= 0, "Should never have a negative ref count after decrementing");
+                    }
+
+                    // Finalization is purely to decrement the ref count.  We can suppress it now.
+                    GC.SuppressFinalize(this);
+                }
+            }
+
+            public bool MoveNext()
+            {
+                // Start by getting the current table.  If it's already been disposed, it will be null.
+                ConditionalWeakTable<TKey, TValue> table = _table;
+                if (table != null)
+                {
+                    // Once have the table, we need to lock to synchronize with other operations on
+                    // the table, like adding.
+                    lock (table._lock)
+                    {
+                        // From the table, we have to get the current container.  This could have changed
+                        // since we grabbed the enumerator, but the index-to-pair mapping should not have
+                        // due to there being at least one active enumerator.  If the table (or rather its
+                        // container at the time) has already been finalized, this will be null.
+                        Container c = table._container;
+                        if (c != null)
+                        {
+                            // We have the container.  Find the next entry to return, if there is one.
+                            // We need to loop as we may try to get an entry that's already been removed
+                            // or collected, in which case we try again.
+                            while (_currentIndex < _maxIndexInclusive)
+                            {
+                                _currentIndex++;
+                                TKey key;
+                                TValue value;
+                                if (c.TryGetEntry(_currentIndex, out key, out value))
+                                {
+                                    _current = new KeyValuePair<TKey, TValue>(key, value);
+                                    return true;
+                                }
+                            }
+                        }
+                    }
+                }
+
+                // Nothing more to enumerate.
+                return false;
+            }
+
+            public KeyValuePair<TKey, TValue> Current
+            {
+                get
+                {
+                    if (_currentIndex < 0)
+                    {
+                        ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
+                    }
+                    return _current;
+                }
+            }
+
+            object IEnumerator.Current => Current;
+
+            public void Reset() { }
+        }
+
         #endregion
 
         #region Internal members
@@ -305,17 +475,6 @@ namespace System.Runtime.CompilerServices
             }
         }
 
-        //--------------------------------------------------------------------------------------------
-        // Clear all the key/value pairs
-        //--------------------------------------------------------------------------------------------
-        internal void Clear()
-        {
-            lock (_lock)
-            {
-                _container = new Container(this);
-            }
-        }
-
         #endregion
 
         #region Private Members
@@ -435,6 +594,8 @@ namespace System.Runtime.CompilerServices
 
             internal bool HasCapacity => _firstFreeEntry < _entries.Length;
 
+            internal int FirstFreeEntry => _firstFreeEntry;
+
             //----------------------------------------------------------------------------------------
             // Worker for adding a new key/value pair.
             // Preconditions:
@@ -508,6 +669,44 @@ namespace System.Runtime.CompilerServices
                 return -1;
             }
 
+            //----------------------------------------------------------------------------------------
+            // Gets the entry at the specified entry index.
+            //----------------------------------------------------------------------------------------
+            internal bool TryGetEntry(int index, out TKey key, out TValue value)
+            {
+                if (index < _entries.Length)
+                {
+                    object oKey, oValue;
+                    _entries[index].depHnd.GetPrimaryAndSecondary(out oKey, out oValue);
+                    GC.KeepAlive(this); // ensure we don't get finalized while accessing DependentHandles.
+
+                    if (oKey != null)
+                    {
+                        key = JitHelpers.UnsafeCast<TKey>(oKey);
+                        value = JitHelpers.UnsafeCast<TValue>(oValue);
+                        return true;
+                    }
+                }
+
+                key = default(TKey);
+                value = default(TValue);
+                return false;
+            }
+
+            //----------------------------------------------------------------------------------------
+            // Removes all of the keys in the table.
+            //----------------------------------------------------------------------------------------
+            internal void RemoveAllKeys()
+            {
+                for (int i = 0; i < _firstFreeEntry; i++)
+                {
+                    RemoveIndex(i);
+                }
+            }
+
+            //----------------------------------------------------------------------------------------
+            // Removes the specified key from the table, if it exists.
+            //----------------------------------------------------------------------------------------
             internal bool Remove(TKey key)
             {
                 VerifyIntegrity();
@@ -516,22 +715,27 @@ namespace System.Runtime.CompilerServices
                 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);
-
+                    RemoveIndex(entryIndex);
                     return true;
                 }
 
                 return false;
             }
 
+            private void RemoveIndex(int entryIndex)
+            {
+                Debug.Assert(entryIndex >= 0 && entryIndex < _firstFreeEntry);
+
+                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);
+            }
 
             internal void UpdateValue(int entryIndex, TValue newValue)
             {
@@ -556,25 +760,33 @@ namespace System.Runtime.CompilerServices
             //----------------------------------------------------------------------------------------
             internal Container Resize()
             {
-                // Start by assuming we won't resize.
-                int newSize = _buckets.Length;
+                Debug.Assert(!HasCapacity);
 
-                // If any expired or removed keys exist, we won't resize.
                 bool hasExpiredEntries = false;
-                for (int entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
+                int newSize = _buckets.Length;
+
+                if (_parent == null || _parent._activeEnumeratorRefCount == 0)
                 {
-                    if (_entries[entriesIndex].HashCode == -1)
+                    // If any expired or removed keys exist, we won't resize.
+                    // If there any active enumerators, though, we don't want
+                    // to compact and thus have no expired entries.
+                    for (int entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
                     {
-                        // the entry was removed
-                        hasExpiredEntries = true;
-                        break;
-                    }
+                        ref Entry entry = ref _entries[entriesIndex];
 
-                    if (_entries[entriesIndex].depHnd.IsAllocated && _entries[entriesIndex].depHnd.GetPrimary() == null)
-                    {
-                        // the entry has expired
-                        hasExpiredEntries = true;
-                        break;
+                        if (entry.HashCode == -1)
+                        {
+                            // the entry was removed
+                            hasExpiredEntries = true;
+                            break;
+                        }
+
+                        if (entry.depHnd.IsAllocated && entry.depHnd.GetPrimary() == null)
+                        {
+                            // the entry has expired
+                            hasExpiredEntries = true;
+                            break;
+                        }
                     }
                 }
 
@@ -585,44 +797,73 @@ namespace System.Runtime.CompilerServices
                 }
 
                 return Resize(newSize);
-            }
+            }            
 
             internal Container Resize(int newSize)
             {
+                Debug.Assert(newSize >= _buckets.Length);
                 Debug.Assert(IsPowerOfTwo(newSize));
 
                 // 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++)
+                for (int bucketIndex = 0; bucketIndex < newBuckets.Length; bucketIndex++)
                 {
                     newBuckets[bucketIndex] = -1;
                 }
                 Entry[] newEntries = new Entry[newSize];
                 int newEntriesIndex = 0;
+                bool activeEnumerators = _parent != null && _parent._activeEnumeratorRefCount > 0;
 
                 // Migrate existing entries to the new table.
-                for (int entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
+                if (activeEnumerators)
                 {
-                    int hashCode = _entries[entriesIndex].HashCode;
-                    DependentHandle depHnd = _entries[entriesIndex].depHnd;
-                    if (hashCode != -1 && depHnd.IsAllocated)
+                    // There's at least one active enumerator, which means we don't want to
+                    // remove any expired/removed entries, in order to not affect existing
+                    // entries indices.  Copy over the entries while rebuilding the buckets list,
+                    // as the buckets are dependent on the buckets list length, which is changing.
+                    for (; newEntriesIndex < _entries.Length; newEntriesIndex++)
                     {
-                        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
+                        ref Entry oldEntry = ref _entries[newEntriesIndex];
+                        ref Entry newEntry = ref newEntries[newEntriesIndex];
+                        int hashCode = oldEntry.HashCode;
+
+                        newEntry.HashCode = hashCode;
+                        newEntry.depHnd = oldEntry.depHnd;
+                        int bucket = hashCode & (newBuckets.Length - 1);
+                        newEntry.Next = newBuckets[bucket];
+                        newBuckets[bucket] = newEntriesIndex;
+                    }
+                }
+                else
+                {
+                    // There are no active enumerators, which means we want to compact by
+                    // removing expired/removed entries.
+                    for (int entriesIndex = 0; entriesIndex < _entries.Length; entriesIndex++)
+                    {
+                        ref Entry oldEntry = ref _entries[entriesIndex];
+                        int hashCode = oldEntry.HashCode;
+                        DependentHandle depHnd = oldEntry.depHnd;
+                        if (hashCode != -1 && depHnd.IsAllocated)
                         {
-                            // Pretend the item was removed, so that this container's finalizer
-                            // will clean up this dependent handle.
-                            Volatile.Write(ref _entries[entriesIndex].HashCode, -1);
+                            if (depHnd.GetPrimary() != null)
+                            {
+                                ref Entry newEntry = ref newEntries[newEntriesIndex];
+
+                                // Entry is used and has not expired. Link it into the appropriate bucket list.
+                                newEntry.HashCode = hashCode;
+                                newEntry.depHnd = depHnd;
+                                int bucket = hashCode & (newBuckets.Length - 1);
+                                newEntry.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 oldEntry.HashCode, -1);
+                            }
                         }
                     }
                 }
@@ -632,6 +873,14 @@ namespace System.Runtime.CompilerServices
                 // 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);
+                if (activeEnumerators)
+                {
+                    // If there are active enumerators, both the old container and the new container may be storing
+                    // the same entries with -1 hash codes, which the finalizer will clean up even if the container
+                    // is not the active container for the table.  To prevent that, we want to stop the old container
+                    // from being finalized, as it no longer has any responsibility for any cleanup.
+                    GC.SuppressFinalize(this);
+                }
                 _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.
@@ -815,7 +1064,6 @@ namespace System.Runtime.CompilerServices
     // This struct intentionally does no self-synchronization. It's up to the caller to
     // to use DependentHandles in a thread-safe way.
     //=========================================================================================
-    [ComVisible(false)]
     internal struct DependentHandle
     {
         #region Constructors