From 5548429858e7d248f08f77b343a2ad60133cb4c0 Mon Sep 17 00:00:00 2001 From: Stephen Toub Date: Wed, 7 Dec 2016 16:35:03 -0500 Subject: [PATCH] Fix perf regression with lots of objects in a ConditionalWeakTable The CoreRT implementation of ConditionalWeakTable that was ported back to CoreCLR uses a special scheme to make reads lock-free. When the container needs to grow, it allocates new arrays and duplicates all of the dependency handles from the previous array, rather than just copying them. This avoids issues stemming from a thread getting a dependency handle in an operation on the container, then having that handle destroyed, and then trying to use it; the handle won't be destroyed as long as the container is referenced. However, this also leads to a significant cost in a certain situation. Every time the container grows, it allocates another N dependency handles where N is the current size of the container. So, for example, with an initial size of 8, if 64 objects are added to the container, it'll allocate 8 dependency handles, then another 16, then another 32, and then another 64, resulting in significantly more handles than in the old implementation, which would only allocate 64 handles total. This commit fixes that by changing the scheme slightly. A container still frees its handles in its finalizer. However, rather than duplicating all handles, that responsibility for freeing is transferred from one container to the next. Then to avoid issues where, for example, the second container is released while the first is still in use, a reference is maintained from the first to the second, so that the second can't be finalized while the first is still in use. The commit also fixes a race condition with resurrection and finalization, whereby dependency handles could be used while or after they're being freed by the finalizer. It's addressed by only freeing handles in a second finalization after clearing out state in the first finalization to guarantee no possible usage during the second. Commit migrated from https://github.com/dotnet/coreclr/commit/03525a46e5d9b33e13a992d89dda3fbf36f43888 --- .../CompilerServices/ConditionalWeakTable.cs | 126 ++++++++++++++++----- 1 file changed, 95 insertions(+), 31 deletions(-) diff --git a/src/coreclr/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs b/src/coreclr/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs index fa8befe..0a1eb15 100644 --- a/src/coreclr/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs +++ b/src/coreclr/src/mscorlib/src/System/Runtime/CompilerServices/ConditionalWeakTable.cs @@ -73,9 +73,17 @@ namespace System.Runtime.CompilerServices where TValue : class { #region Fields - private const int InitialCapacity = 8; // Must be a power of two - private readonly object _lock = new object(); // This lock protects all mutation of data in the table. Readers do not take this lock. - private volatile Container _container = new Container(); + 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 + public ConditionalWeakTable() + { + _lock = new object(); + _container = new Container(this); + } #endregion #region Public Members @@ -273,7 +281,7 @@ namespace System.Runtime.CompilerServices { lock (_lock) { - _container = new Container(); + _container.Clear(); } } @@ -352,14 +360,19 @@ namespace System.Runtime.CompilerServices // private sealed class Container { - private int[] _buckets; // _buckets[hashcode & (_buckets.Length - 1)] contains index of the first entry in bucket (-1 if empty) - private Entry[] _entries; - 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. - - internal Container() + private readonly ConditionalWeakTable _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 parent) { + Debug.Assert(parent != null); Debug.Assert(IsPowerOfTwo(InitialCapacity)); + int size = InitialCapacity; _buckets = new int[size]; for (int i = 0; i < _buckets.Length; i++) @@ -367,10 +380,23 @@ namespace System.Runtime.CompilerServices _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; } - private Container(int[] buckets, Entry[] entries, int firstFreeEntry) + private Container(ConditionalWeakTable 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; @@ -469,6 +495,16 @@ namespace System.Runtime.CompilerServices return false; } + internal void Clear() + { + // Remove all handles (as in Remove, just by setting the hashcode and leaving + // actual removal up to the finalizer). + for (int i = 0; i < _firstFreeEntry; i++) + { + Volatile.Write(ref _entries[i].HashCode, -1); + } + } + //---------------------------------------------------------------------------------------- // This does two things: resize and scrub expired keys off bucket lists. // @@ -537,21 +573,32 @@ namespace System.Runtime.CompilerServices if (primary != null) { // Entry is used and has not expired. Link it into the appropriate bucket list. - // Note that we have to copy the DependentHandle, since the original copy will be freed - // by the Container's finalizer. newEntries[newEntriesIndex].HashCode = hashCode; - newEntries[newEntriesIndex].depHnd = depHnd.AllocateCopy(); + 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 new Container(newBuckets, newEntries, newEntriesIndex); + return newContainer; } internal ICollection Keys @@ -650,19 +697,36 @@ namespace System.Runtime.CompilerServices ~Container() { // 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.) + // 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) + { + return; + } - if (Environment.HasShutdownStarted || _invalid) + // 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) + { + if (_parent._container == this) + { + _parent._container = null; + } + } + GC.ReRegisterForFinalize(this); // next time it's finalized, we'll be sure there are no remaining refs return; } Entry[] entries = _entries; - - // 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; @@ -671,7 +735,15 @@ namespace System.Runtime.CompilerServices { 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(); + } } } } @@ -716,14 +788,6 @@ namespace System.Runtime.CompilerServices // no need to check for null result: nInitialize expected to throw OOM. _handle = handle; } - - public DependentHandle AllocateCopy() - - { - object primary, secondary; - GetPrimaryAndSecondary(out primary, out secondary); - return new DependentHandle(primary, secondary); - } #endregion #region Public Members -- 2.7.4