|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Diagnostics;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
namespace System.Threading
{
/// <summary>
/// Stores the hash code and the Monitor synchronization object for all managed objects used
/// with the Monitor.Enter/TryEnter/Exit methods.
/// </summary>
/// <remarks>
/// This implementation is faster than ConditionalWeakTable since we store the synchronization
/// entry index in the object header, which avoids a hash table lookup. It closely matches
/// implementation of SyncBlocks.
///
/// SyncTable assigns a unique table entry to each object it is asked for. The assigned entry
/// index is stored in the object header and preserved during table expansion (we never shrink
/// the table). Each table entry contains a long weak GC handle representing the owner object
/// of that entry and may be in one of the three states:
/// 1) Free (IsAllocated == false). These entries have been either never used or used and
/// freed/recycled after their owners died. We keep a linked list of recycled entries and
/// use it to dispense entries to new objects.
/// 2) Live (Target != null). These entries store the hash code and the Monitor synchronization
/// object assigned to Target.
/// 3) Dead (Target == null). These entries lost their owners and are ready to be freed/recycled.
///
/// Here is the state diagram for an entry:
/// Free --{AssignEntry}--> Live --{GC}--> Dead --{(Recycle|Free)DeadEntries} --> Free
///
/// The public methods operates on live entries only and acquire the following locks:
/// * GetLockObject : Lock-free. We always allocate a Monitor synchronization object before
/// the entry goes live. The returned object may be used as normal; no
/// additional synchronization required.
/// * GetHashCode : Lock-free. A stale zero value may be returned.
/// * SetHashCode : Acquires s_lock.
/// * AssignEntry : Acquires s_lock.
///
/// The important part here is that all read operations are lock-free and fast, and write
/// operations are expected to be much less frequent than read ones.
///
/// </remarks>
[EagerStaticClassConstruction]
internal static class SyncTable
{
/// <summary>
/// The initial size of the table. Must be positive and not greater than
/// ObjectHeader.MASK_HASHCODE_INDEX + 1.
/// </summary>
#if DEBUG
// Exercise table expansion more frequently in debug builds
private const int InitialSize = 1;
#else
private const int InitialSize = 1 << 7;
#endif
/// <summary>
/// The table size threshold for doubling in size. Must be positive.
/// </summary>
private const int DoublingSizeThreshold = 1 << 20;
/// <summary>
/// Protects all mutable operations on s_entries, s_freeEntryList, s_unusedEntryIndex. Also protects growing the table.
/// </summary>
internal static readonly Lock s_lock = new Lock(useTrivialWaits: true);
/// <summary>
/// The dynamically growing array of sync entries.
/// </summary>
private static Entry[] s_entries = new Entry[InitialSize];
/// <summary>
/// The head of the list of freed entries linked using the Next property.
/// </summary>
private static int s_freeEntryList;
/// <summary>
/// The index of the lowest never used entry. We skip the 0th entry and start with 1.
/// If all entries have been used, s_unusedEntryIndex == s_entries.Length. This counter
/// never decreases.
/// </summary>
private static int s_unusedEntryIndex = 1;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static ref Entry UnsafeEntryRef(int i)
{
#if DEBUG
return ref s_entries[i];
#else
return ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(s_entries), i);
#endif
}
/// <summary>
/// Assigns a sync table entry to the object in a thread-safe way.
/// </summary>
public static unsafe int AssignEntry(object obj, int* pHeader)
{
// Allocate the synchronization object outside the lock
Lock lck = new Lock();
DeadEntryCollector collector = new DeadEntryCollector();
DependentHandle handle = new DependentHandle(obj, collector);
try
{
using (s_lock.EnterScope())
{
// After acquiring the lock check whether another thread already assigned the sync entry
if (ObjectHeader.GetSyncEntryIndex(*pHeader, out int syncIndex))
{
return syncIndex;
}
if (s_freeEntryList != 0)
{
// Grab a free entry from the list
syncIndex = s_freeEntryList;
ref Entry freeEntry = ref s_entries[syncIndex];
s_freeEntryList = freeEntry.Next;
freeEntry.Next = 0;
}
else
{
if (s_unusedEntryIndex >= s_entries.Length)
{
// No free entries, use the slow path. This call may OOM.
Grow();
}
// Grab the next unused entry
Debug.Assert(s_unusedEntryIndex < s_entries.Length);
syncIndex = s_unusedEntryIndex++;
}
ref Entry entry = ref s_entries[syncIndex];
// Found a free entry to assign
Debug.Assert(!entry.Owner.IsAllocated);
Debug.Assert(entry.Lock is null);
Debug.Assert(entry.HashCode == 0);
// Set up the new entry. We should not fail after this point.
entry.Lock = lck;
// The hash code will be set by the SetSyncEntryIndex call below
entry.Owner = handle;
handle = default;
collector.Activate(syncIndex);
collector = default!;
// Finally, store the entry index in the object header
ObjectHeader.SetSyncEntryIndex(pHeader, syncIndex);
return syncIndex;
}
}
finally
{
if (collector != null)
GC.SuppressFinalize(collector);
handle.Dispose();
}
}
/// <summary>
/// Grows the sync table. If memory is not available, it throws an OOM exception keeping
/// the state valid.
/// </summary>
private static void Grow()
{
Debug.Assert(s_lock.IsHeldByCurrentThread);
int oldSize = s_entries.Length;
int newSize = CalculateNewSize(oldSize);
Entry[] newEntries = new Entry[newSize];
// Copy the shallow content of the table
Array.Copy(s_entries, newEntries, oldSize);
// Publish the new table. Lock-free reader threads must not see the new value of
// s_entries until all the content is copied to the new table.
Volatile.Write(ref s_entries, newEntries);
}
/// <summary>
/// Calculates the new size of the sync table if it needs to grow. Throws an OOM exception
/// in case of size overflow.
/// </summary>
private static int CalculateNewSize(int oldSize)
{
Debug.Assert(oldSize > 0);
Debug.Assert(ObjectHeader.MASK_HASHCODE_INDEX < int.MaxValue);
int newSize;
if (oldSize <= DoublingSizeThreshold)
{
// Double in size; overflow is checked below
newSize = unchecked(oldSize * 2);
}
else
{
// For bigger tables use a smaller factor 1.5
Debug.Assert(oldSize > 1);
newSize = unchecked(oldSize + (oldSize >> 1));
}
// All indices must fit in the mask, limit the size accordingly
newSize = Math.Min(newSize, ObjectHeader.MASK_HASHCODE_INDEX + 1);
// Make sure the new size has not overflowed and is actually bigger
if (newSize <= oldSize)
{
throw new OutOfMemoryException();
}
return newSize;
}
/// <summary>
/// Returns the stored hash code. The zero value indicates the hash code has not yet been
/// assigned or visible to this thread.
/// </summary>
public static int GetHashCode(int syncIndex)
{
// This thread may be looking at an old version of s_entries. If the old version had
// no hash code stored, GetHashCode returns zero and the subsequent SetHashCode call
// will resolve the potential race.
return UnsafeEntryRef(syncIndex).HashCode;
}
/// <summary>
/// Sets the hash code in a thread-safe way.
/// </summary>
public static int SetHashCode(int syncIndex, int hashCode)
{
Debug.Assert((0 < syncIndex) && (syncIndex < s_unusedEntryIndex));
// Acquire the lock to ensure we are updating the latest version of s_entries. This
// lock may be avoided if we store the hash code and Monitor synchronization data in
// the same object accessed by a reference.
using (s_lock.EnterScope())
{
int currentHash = s_entries[syncIndex].HashCode;
if (currentHash != 0)
{
return currentHash;
}
s_entries[syncIndex].HashCode = hashCode;
return hashCode;
}
}
/// <summary>
/// Sets the hash code assuming the caller holds s_lock. Use for not yet
/// published entries only.
/// </summary>
public static void MoveHashCodeToNewEntry(int syncIndex, int hashCode)
{
Debug.Assert(s_lock.IsHeldByCurrentThread);
Debug.Assert((0 < syncIndex) && (syncIndex < s_unusedEntryIndex));
s_entries[syncIndex].HashCode = hashCode;
}
/// <summary>
/// Initializes the Lock assuming the caller holds s_lock. Use for not yet
/// published entries only.
/// </summary>
public static void MoveThinLockToNewEntry(int syncIndex, int threadId, uint recursionLevel)
{
Debug.Assert(s_lock.IsHeldByCurrentThread);
Debug.Assert((0 < syncIndex) && (syncIndex < s_unusedEntryIndex));
s_entries[syncIndex].Lock.InitializeForMonitor(threadId, recursionLevel);
}
/// <summary>
/// Returns the Monitor synchronization object. The return value is never null.
/// </summary>
public static Lock GetLockObject(int syncIndex)
{
// Note that we do not take a lock here. When we replace s_entries, we preserve all
// indices and Lock references.
return UnsafeEntryRef(syncIndex).Lock;
}
private sealed class DeadEntryCollector
{
private int _index;
public DeadEntryCollector()
{
}
public void Activate(int index) => _index = index;
~DeadEntryCollector()
{
if (_index == 0)
return;
Lock? lockToDispose = default;
DependentHandle dependentHandleToDispose = default;
using (s_lock.EnterScope())
{
ref Entry entry = ref s_entries[_index];
if (entry.Owner.Target != null)
{
// Retry later if the owner is not collected yet.
GC.ReRegisterForFinalize(this);
return;
}
dependentHandleToDispose = entry.Owner;
entry.Owner = default;
lockToDispose = entry.Lock;
entry.Lock = default;
entry.Next = s_freeEntryList;
s_freeEntryList = _index;
}
// Dispose outside the lock
dependentHandleToDispose.Dispose();
lockToDispose?.Dispose();
}
}
/// <summary>
/// Stores the Monitor synchronization object and the hash code for an arbitrary object.
/// </summary>
private struct Entry
{
/// <summary>
/// The Monitor synchronization object.
/// </summary>
public Lock Lock;
/// <summary>
/// Contains either the hash code or the index of the next freed entry.
/// </summary>
private int _hashOrNext;
/// <summary>
/// The dependent GC handle representing the owner object of this sync entry and the collector responsible
/// for freeing the entry.
/// </summary>
public DependentHandle Owner;
// Unused field to make the entry even number of words.
// we will likely put something in here eventually.
internal nint _unusedPadding;
/// <summary>
/// For entries in use, this property gets or sets the hash code of the owner object.
/// The zero value indicates the hash code has not yet been assigned.
/// </summary>
public int HashCode
{
get { return _hashOrNext; }
set { _hashOrNext = value; }
}
/// <summary>
/// For freed entries, this property gets or sets the index of the next freed entry.
/// The zero value indicates the end of the list.
/// </summary>
public int Next
{
get { return _hashOrNext; }
set { _hashOrNext = value; }
}
}
}
}
|