Replace multi-loaderallocator hash implementation in MethodDescBackpatchInfo (#22285)

* GCHeapHash
- Hashtable implementation for runtime use
- Implementation written in C++
- Data storage in managed heap memory
- Based on SHash design, but using managed memory

CrossLoaderAllocatorHash
- Hash for c++ Pointer to C++ pointer where the lifetimes are controlled by different loader allocators
 - Support for add/remove/visit all entries of 1 key/visit all entries/ remove all entries of 1 key
- Supports holding data which is unmanaged, but data items themselves can be of any size (key/value are templated types)

* Swap MethodDescBackpatchInfo to use the CrossLoaderAllocatorHash

* The MethodDescBackpatchCrst needs to be around an allocation
- Adjust the Crst so that it can safely be used around code which allocates
- Required moving its use out from within the EESuspend logic used in rejit

1 files changed, 197 insertions, 0 deletions

diff --git a/src/vm/crossloaderallocatorhash.h b/src/vm/crossloaderallocatorhash.h
new file mode 100644
index 0000000000..09068752b0
--- /dev/null
+++ b/src/vm/crossloaderallocatorhash.h
@@ -0,0 +1,197 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+#ifndef CROSSLOADERALLOCATORHASH_H
+#define CROSSLOADERALLOCATORHASH_H
+#ifndef CROSSGEN_COMPILE
+
+#include "gcheaphashtable.h"
+
+class LoaderAllocator;
+
+template <class TKey_, class TValue_>
+class NoRemoveDefaultCrossLoaderAllocatorHashTraits
+{
+public:
+    typedef TKey_ TKey;
+    typedef TValue_ TValue;
+
+    static bool IsNull(const TValue &value) { return value == NULL; }
+    static TValue NullValue() { return NULL; }
+
+#ifndef DACCESS_COMPILE
+    static void SetUsedEntries(TValue* pStartOfValuesData, DWORD entriesInArrayTotal, DWORD usedEntries);
+    static bool AddToValuesInHeapMemory(OBJECTREF *pKeyValueStore, const TKey& key, const TValue& value);
+#endif //!DACCESS_COMPILE
+    static DWORD ComputeUsedEntries(OBJECTREF *pKeyValueStore, DWORD *pEntriesInArrayTotal);
+    template <class Visitor>
+    static bool VisitKeyValueStore(OBJECTREF *pLoaderAllocatorRef, OBJECTREF *pKeyValueStore, Visitor &visitor);
+    static TKey ReadKeyFromKeyValueStore(OBJECTREF *pKeyValueStore);
+};
+
+template <class TKey_, class TValue_>
+class DefaultCrossLoaderAllocatorHashTraits : public NoRemoveDefaultCrossLoaderAllocatorHashTraits<TKey_, TValue_>
+{
+public:
+    typedef TKey_ TKey;
+    typedef TValue_ TValue;
+
+#ifndef DACCESS_COMPILE
+    static void DeleteValueInHeapMemory(OBJECTREF keyValueStore, const TValue& value);
+#endif //!DACCESS_COMPILE
+};
+
+struct GCHeapHashDependentHashTrackerHashTraits : public DefaultGCHeapHashTraits<true>
+{
+    typedef LoaderAllocator* PtrTypeKey;
+
+    static INT32 Hash(PtrTypeKey *pValue);
+    static INT32 Hash(PTRARRAYREF arr, INT32 index);
+    static bool DoesEntryMatchKey(PTRARRAYREF arr, INT32 index, PtrTypeKey *pKey);
+    static bool IsDeleted(PTRARRAYREF arr, INT32 index, GCHEAPHASHOBJECTREF gcHeap);
+};
+
+typedef GCHeapHash<GCHeapHashDependentHashTrackerHashTraits> GCHeapHashDependentHashTrackerHash;
+
+template<class TRAITS>
+struct KeyToValuesGCHeapHashTraits : public DefaultGCHeapHashTraits<true>
+{
+    template <class TKey>
+    static INT32 Hash(TKey *pValue);
+    static INT32 Hash(PTRARRAYREF arr, INT32 index);
+
+    template<class TKey>
+    static bool DoesEntryMatchKey(PTRARRAYREF arr, INT32 index, TKey *pKey);
+};
+
+// Hashtable of key to a list of values where the key may live in a different loader allocator
+// than the value and this should not keep the loaderallocator of the value alive. The type of
+// keys/values is defined via the TRAITS template argument, but must be non-gc pointers, and
+// must be copyable without a copy constructor/require a destructor.
+//
+// This is managed via a series of different hashtables and data structures that are carefully
+// engineered to be relatively memory efficient, yet still provide the ability to safely use
+// the hashtable to hold relationships across LoaderAllocators which are not generally safe.
+//
+// In particular, given LoaderAllocator LA1 and LA2, where a reference to LA1 is not
+// guaranteed to keep LA2 alive, this data structure can permit a pointer to an object which
+// is defined as part of LA1 to be used as a key to find a pointer to an object that has the
+// same lifetime as LA2.
+//
+// This data structure exposes Remove api's, but its primary use case is the combination of
+// the Add and VisitValuesOfKey apis.
+//
+// To use Add, simply, call Add(TKey key, TValue value). This will add to the list of values
+// associated with a key. The Add api should be called on a key's which are associated with
+// the same LoaderAllocator as the CrossLoaderAllocatorHash.
+//
+// VisitValuesOfKey will visit all values that have the same key.
+//
+// IMPLEMENTATION DESIGN
+// This data structure is a series of hashtables and lists.
+// 
+// In general, this data structure builds a set of values associated with a key per
+// LoaderAllocator. The lists per loader allocator are controlled via the TRAITS template. The
+// TRAITS specify how the individual lists are handled, and do the copying in and out of the data
+// structures. It is not expected that additional traits implementations will be needed for use,
+// unless duplicate prevention is needed.
+//
+// BASIC STRUCTURE
+//
+// m_keyToDependentTrackersHash - Hashtable of key -> (list of values in primary loader allocator,
+//                                                   hashtable of DependentTrackers)
+//
+//   For each key in the table, there is at list of values in the primary loader allocator,
+//   and optionally there may be a hashtable of dependent trackers
+//
+// m_loaderAllocatorToDependentTrackerHash - Hashtable of LoaderAllocator to DependentTracker. Used to find
+// dependent trackers for insertion into per key sets.
+//
+// The DependentTracker is an object (with a finalizer) which is associated with a specific
+// LoaderAllocator, and uses a DependentHandle to hold onto  a hashtable from Key to List of
+// Values (for a specific LoaderAllocator). This dependent handle will keep that hashtable alive
+// as long as the associated LoaderAllocator is live.
+//
+// The DependentTracker hashes (both the m_loaderAllocatorToDependentTrackerHash, and the per key hashes) are
+// implemented via a hashtable which is "self-cleaning". In particular as the hashtable is
+// walked for Add/Visit/Remove operations, if a DependentTracker is found which where the
+// DependentHandle has detected that the LoaderAllocator has been freed, then the entry in
+// the hashtable will set itself to the DELETED state. This cleaning operation will not occur
+// eagerly, but it should prevent unbounded size growth as collectible LoaderAllocators are
+// allocated and freed.
+//
+// Memory efficiency of this data structure.
+//  - This data structure is reasonably memory efficient. If many values share the same key
+//    then the memory efficiency per key trends toward 1.3333 * sizeof(Value). Otherwise basic
+//    cost per key/value pair (assuming they are pointer sized has an overhead of about 4 
+//    pointers + key/value data size.)
+template <class TRAITS>
+class CrossLoaderAllocatorHash
+{
+private:
+    typedef typename TRAITS::TKey TKey;
+    typedef typename TRAITS::TValue TValue;
+    typedef GCHeapHash<KeyToValuesGCHeapHashTraits<TRAITS>> KeyToValuesGCHeapHash;
+
+public:
+
+#ifndef DACCESS_COMPILE
+    // Add an entry to the CrossLoaderAllocatorHash, the default implementation of does DefaultCrossLoaderAllocatorHashTraits will not check for duplicates.
+    void Add(TKey key, TValue value, LoaderAllocator *pLoaderAllocatorOfValue);
+
+    // Remove an entry to the CrossLoaderAllocatorHash, only removes one entry
+    void Remove(TKey key, TValue value, LoaderAllocator *pLoaderAllocatorOfValue);
+
+    // Remove all entries that can be looked up by key
+    void RemoveAll(TKey key);
+#endif
+
+    // Using visitor walk all values associated with a given key. The visitor
+    // is expected to implement bool operator ()(OBJECTREF keepAlive, TKey key, TValue value).
+    // Return false from that function to stop visitation.
+    // This can be done simply by utilizing a lambda, or if a lambda cannot be used, a functor will do.
+    // The value of "value" in this case must not escape from the visitor object
+    // unless the keepAlive OBJECTREF is also kept alive
+    template <class Visitor>
+    bool VisitValuesOfKey(TKey key, Visitor &visitor);
+
+    // Visit all key/value pairs
+    template <class Visitor>
+    bool VisitAllKeyValuePairs(Visitor &visitor);
+
+    // Initialize this CrossLoaderAllocatorHash to be associated with a specific LoaderAllocator
+    // Must be called before any use of Add
+    void Init(LoaderAllocator *pAssociatedLoaderAllocator);
+
+private:
+#ifndef DACCESS_COMPILE
+    void EnsureManagedObjectsInitted();
+    LAHASHDEPENDENTHASHTRACKERREF GetDependentTrackerForLoaderAllocator(LoaderAllocator* pLoaderAllocator);
+    GCHEAPHASHOBJECTREF GetKeyToValueCrossLAHashForHashkeyToTrackers(LAHASHKEYTOTRACKERSREF hashKeyToTrackersUnsafe, LoaderAllocator* pValueLoaderAllocator);
+#endif // !DACCESS_COMPILE
+    
+    template <class Visitor>
+    static bool VisitKeyValueStore(OBJECTREF *pLoaderAllocatorRef, OBJECTREF *pKeyValueStore, Visitor &visitor);
+    template <class Visitor>
+    static bool VisitTracker(TKey key, LAHASHDEPENDENTHASHTRACKERREF trackerUnsafe, Visitor &visitor);
+    template <class Visitor>
+    static bool VisitTrackerAllEntries(LAHASHDEPENDENTHASHTRACKERREF trackerUnsafe, Visitor &visitor);
+    template <class Visitor>
+    static bool VisitKeyToTrackerAllEntries(OBJECTREF hashKeyEntryUnsafe, Visitor &visitor);
+    static void DeleteEntryTracker(TKey key, LAHASHDEPENDENTHASHTRACKERREF trackerUnsafe);
+
+private:
+    LoaderAllocator *m_pLoaderAllocator = 0;
+    OBJECTHANDLE m_loaderAllocatorToDependentTrackerHash = 0;
+    OBJECTHANDLE m_keyToDependentTrackersHash = 0;
+};
+
+class CrossLoaderAllocatorHashSetup
+{
+public:
+    inline static void EnsureTypesLoaded();
+};
+
+#endif // !CROSSGEN_COMPILE
+#endif // CROSSLOADERALLOCATORHASH_H