diff options
Diffstat (limited to 'src/vm/eehash.h')
| -rw-r--r-- | src/vm/eehash.h | 609 |
1 files changed, 609 insertions, 0 deletions
diff --git a/src/vm/eehash.h b/src/vm/eehash.h new file mode 100644 index 0000000000..8e92ad35d9 --- /dev/null +++ b/src/vm/eehash.h @@ -0,0 +1,609 @@ +// 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. +// + +// +//emp +// File: eehash.h +// +// Provides hash table functionality needed in the EE - intended to be replaced later with better +// algorithms, but which have the same interface. +// +// Two requirements are: +// +// 1. Any number of threads can be reading the hash table while another thread is writing, without error. +// 2. Only one thread can write at a time. +// 3. When calling ReplaceValue(), a reader will get the old value, or the new value, but not something +// in between. +// 4. DeleteValue() is an unsafe operation - no other threads can be in the hash table when this happens. +// + +#ifndef _EE_HASH_H +#define _EE_HASH_H + +#include "exceptmacros.h" +#include "syncclean.hpp" +#ifdef FEATURE_PREJIT +class DataImage; +#endif + +#include "util.hpp" + +#ifdef FEATURE_PREJIT +#include "corcompile.h" +#endif + +class AllocMemTracker; +class ClassLoader; +struct LockOwner; +class NameHandle; +struct PsetCacheKey; +class SigTypeContext; + +typedef PsetCacheKey* PPsetCacheKey; + +// The "blob" you get to store in the hash table + +typedef PTR_VOID HashDatum; + +// The heap that you want the allocation to be done in + +typedef void* AllocationHeap; + + +// One of these is present for each element in the table. +// Update the SIZEOF_EEHASH_ENTRY macro below if you change this +// struct + +typedef struct EEHashEntry EEHashEntry_t; +typedef DPTR(EEHashEntry_t) PTR_EEHashEntry_t; +struct EEHashEntry +{ + PTR_EEHashEntry_t pNext; + DWORD dwHashValue; + HashDatum Data; + BYTE Key[1]; // The key is stored inline +}; + +// The key[1] is a place holder for the key +// SIZEOF_EEHASH_ENTRY is the size of struct up to (and not including) the key +#define SIZEOF_EEHASH_ENTRY (offsetof(EEHashEntry,Key[0])) + + +// Struct to hold a client's iteration state +struct EEHashTableIteration; + +class GCHeap; + +// Generic hash table. + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +class EEHashTableBase +{ +public: + + + BOOL Init(DWORD dwNumBuckets, LockOwner *pLock, AllocationHeap pHeap = 0,BOOL CheckThreadSafety = TRUE); + + void InsertValue(KeyType pKey, HashDatum Data, BOOL bDeepCopyKey = bDefaultCopyIsDeep); + void InsertKeyAsValue(KeyType pKey, BOOL bDeepCopyKey = bDefaultCopyIsDeep); + BOOL DeleteValue(KeyType pKey); + BOOL ReplaceValue(KeyType pKey, HashDatum Data); + BOOL ReplaceKey(KeyType pOldKey, KeyType pNewKey); + void ClearHashTable(); + void EmptyHashTable(); + BOOL IsEmpty(); + void Destroy(); + + // Reader functions. Please place any functions that can be called from the + // reader threads here. + BOOL GetValue(KeyType pKey, HashDatum *pData); + BOOL GetValue(KeyType pKey, HashDatum *pData, DWORD hashValue); + + + // A fast inlinable flavor of GetValue that can return false instead of the actual item + // if there is race with updating of the hashtable. Callers of GetValueSpeculative + // should fall back to the slow GetValue if GetValueSpeculative returns false. + // Assumes that we are in cooperative mode already. For performance-sensitive codepaths. + BOOL GetValueSpeculative(KeyType pKey, HashDatum *pData); + + DWORD GetHash(KeyType Key); + DWORD GetCount(); + + // Walk through all the entries in the hash table, in meaningless order, without any + // synchronization. + // + // IterateStart() + // while (IterateNext()) + // IterateGetKey(); + // + // This is guaranteed to be DeleteValue-friendly if you advance the iterator before + // deletig, i.e. if used in the following pattern: + // + // IterateStart(); + // BOOL keepGoing = IterateNext(); + // while(keepGoing) + // { + // key = IterateGetKey(); + // keepGoing = IterateNext(); + // ... + // DeleteValue(key); + // .. + // } + void IterateStart(EEHashTableIteration *pIter); + BOOL IterateNext(EEHashTableIteration *pIter); + KeyType IterateGetKey(EEHashTableIteration *pIter); + HashDatum IterateGetValue(EEHashTableIteration *pIter); +#ifdef _DEBUG + void SuppressSyncCheck() + { + LIMITED_METHOD_CONTRACT; + m_CheckThreadSafety=FALSE; + } +#endif +protected: + BOOL GrowHashTable(); + EEHashEntry_t * FindItem(KeyType pKey); + EEHashEntry_t * FindItem(KeyType pKey, DWORD hashValue); + + // A fast inlinable flavor of FindItem that can return null instead of the actual item + // if there is race with updating of the hashtable. Callers of FindItemSpeculative + // should fall back to the slow FindItem if FindItemSpeculative returns null. + // Assumes that we are in cooperative mode already. For performance-sensitive codepaths. + EEHashEntry_t * FindItemSpeculative(KeyType pKey, DWORD hashValue); + + // Double buffer to fix the race condition of growhashtable (the update + // of m_pBuckets and m_dwNumBuckets has to be atomic, so we double buffer + // the structure and access it through a pointer, which can be updated + // atomically. The union is in order to not change the SOS macros. + + struct BucketTable + { + DPTR(PTR_EEHashEntry_t) m_pBuckets; // Pointer to first entry for each bucket + DWORD m_dwNumBuckets; + } m_BucketTable[2]; + typedef DPTR(BucketTable) PTR_BucketTable; + + // In a function we MUST only read this value ONCE, as the writer thread can change + // the value asynchronously. We make this member volatile the compiler won't do copy propagation + // optimizations that can make this read happen more than once. Note that we only need + // this property for the readers. As they are the ones that can have + // this variable changed (note also that if the variable was enregistered we wouldn't + // have any problem) + // BE VERY CAREFUL WITH WHAT YOU DO WITH THIS VARIABLE AS USING IT BADLY CAN CAUSE + // RACING CONDITIONS + VolatilePtr<BucketTable, PTR_BucketTable> m_pVolatileBucketTable; + + + DWORD m_dwNumEntries; + AllocationHeap m_Heap; + Volatile<LONG> m_bGrowing; +#ifdef _DEBUG + LPVOID m_lockData; + FnLockOwner m_pfnLockOwner; + + EEThreadId m_writerThreadId; + BOOL m_CheckThreadSafety; + +#endif + +#ifdef _DEBUG_IMPL + // A thread must own a lock for a hash if it is a writer. + BOOL OwnLock(); +#endif // _DEBUG_IMPL +}; + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +class EEHashTable : public EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep> +{ +public: + EEHashTable() + { + LIMITED_METHOD_CONTRACT; + this->m_BucketTable[0].m_pBuckets = NULL; + this->m_BucketTable[0].m_dwNumBuckets = 0; + this->m_BucketTable[1].m_pBuckets = NULL; + this->m_BucketTable[1].m_dwNumBuckets = 0; +#ifndef DACCESS_COMPILE + this->m_pVolatileBucketTable = NULL; +#endif + this->m_dwNumEntries = 0; + this->m_bGrowing = 0; +#ifdef _DEBUG + this->m_lockData = NULL; + this->m_pfnLockOwner = NULL; +#endif + } + + ~EEHashTable() + { + WRAPPER_NO_CONTRACT; + this->Destroy(); + } +}; + +/* to be used as static variable - no constructor/destructor, assumes zero + initialized memory */ +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +class EEHashTableStatic : public EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep> +{ +}; + +class EEIntHashTableHelper +{ +public: + static EEHashEntry_t *AllocateEntry(int iKey, BOOL bDeepCopy, AllocationHeap pHeap = 0) + { + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(return NULL;); + } + CONTRACTL_END + + _ASSERTE(!bDeepCopy && "Deep copy is not supported by the EEPtrHashTableHelper"); + + EEHashEntry_t *pEntry = (EEHashEntry_t *) new (nothrow) BYTE[SIZEOF_EEHASH_ENTRY + sizeof(int)]; + if (!pEntry) + return NULL; + *((int*) pEntry->Key) = iKey; + + return pEntry; + } + + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap pHeap = 0) + { + LIMITED_METHOD_CONTRACT; + + // Delete the entry. + delete [] (BYTE*) pEntry; + } + + static BOOL CompareKeys(EEHashEntry_t *pEntry, int iKey) + { + LIMITED_METHOD_CONTRACT; + + return *((int*)pEntry->Key) == iKey; + } + + static DWORD Hash(int iKey) + { + LIMITED_METHOD_CONTRACT; + + return (DWORD)iKey; + } + + static int GetKey(EEHashEntry_t *pEntry) + { + LIMITED_METHOD_CONTRACT; + + return *((int*) pEntry->Key); + } +}; +typedef EEHashTable<int, EEIntHashTableHelper, FALSE> EEIntHashTable; + +typedef struct PtrPlusInt +{ + void* pValue; + int iValue; +} *PPtrPlusInt; + +class EEPtrPlusIntHashTableHelper +{ +public: + static EEHashEntry_t *AllocateEntry(PtrPlusInt ppiKey, BOOL bDeepCopy, AllocationHeap pHeap = 0) + { + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(return NULL;); + } + CONTRACTL_END + + _ASSERTE(!bDeepCopy && "Deep copy is not supported by the EEPtrPlusIntHashTableHelper"); + + EEHashEntry_t *pEntry = (EEHashEntry_t *) new (nothrow) BYTE[SIZEOF_EEHASH_ENTRY + sizeof(PtrPlusInt)]; + if (!pEntry) + return NULL; + *((PPtrPlusInt) pEntry->Key) = ppiKey; + + return pEntry; + } + + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap pHeap = 0) + { + LIMITED_METHOD_CONTRACT; + + // Delete the entry. + delete [] (BYTE*) pEntry; + } + + static BOOL CompareKeys(EEHashEntry_t *pEntry, PtrPlusInt ppiKey) + { + LIMITED_METHOD_CONTRACT; + + return (((PPtrPlusInt)pEntry->Key)->pValue == ppiKey.pValue) && + (((PPtrPlusInt)pEntry->Key)->iValue == ppiKey.iValue); + } + + static DWORD Hash(PtrPlusInt ppiKey) + { + LIMITED_METHOD_CONTRACT; + + return (DWORD)ppiKey.iValue ^ +#ifdef _TARGET_X86_ + (DWORD)(size_t) ppiKey.pValue; +#else + // <TODO> IA64: Is this a good hashing mechanism on IA64?</TODO> + (DWORD)(((size_t) ppiKey.pValue) >> 3); +#endif + } + + static PtrPlusInt GetKey(EEHashEntry_t *pEntry) + { + LIMITED_METHOD_CONTRACT; + + return *((PPtrPlusInt) pEntry->Key); + } +}; + +typedef EEHashTable<PtrPlusInt, EEPtrPlusIntHashTableHelper, FALSE> EEPtrPlusIntHashTable; + +// UTF8 string hash table. The UTF8 strings are NULL terminated. + +class EEUtf8HashTableHelper +{ +public: + static EEHashEntry_t * AllocateEntry(LPCUTF8 pKey, BOOL bDeepCopy, AllocationHeap Heap); + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap); + static BOOL CompareKeys(EEHashEntry_t *pEntry, LPCUTF8 pKey); + static DWORD Hash(LPCUTF8 pKey); + static LPCUTF8 GetKey(EEHashEntry_t *pEntry); +}; + +typedef EEHashTable<LPCUTF8, EEUtf8HashTableHelper, TRUE> EEUtf8StringHashTable; +typedef DPTR(EEUtf8StringHashTable) PTR_EEUtf8StringHashTable; + +// Unicode String hash table - the keys are UNICODE strings which may +// contain embedded nulls. An EEStringData struct is used for the key +// which contains the length of the item. Note that this string is +// not necessarily null terminated and should never be treated as such. +const DWORD ONLY_LOW_CHARS_MASK = 0x80000000; + +class EEStringData +{ +private: + LPCWSTR szString; // The string data. + DWORD cch; // Characters in the string. +#ifdef _DEBUG + BOOL bDebugOnlyLowChars; // Does the string contain only characters less than 0x80? + DWORD dwDebugCch; +#endif // _DEBUG + +public: + // explicilty initialize cch to 0 because SetCharCount uses cch + EEStringData() : cch(0) + { + LIMITED_METHOD_CONTRACT; + + SetStringBuffer(NULL); + SetCharCount(0); + SetIsOnlyLowChars(FALSE); + }; + EEStringData(DWORD cchString, LPCWSTR str) : cch(0) + { + LIMITED_METHOD_CONTRACT; + + SetStringBuffer(str); + SetCharCount(cchString); + SetIsOnlyLowChars(FALSE); + }; + EEStringData(DWORD cchString, LPCWSTR str, BOOL onlyLow) : cch(0) + { + LIMITED_METHOD_CONTRACT; + + SetStringBuffer(str); + SetCharCount(cchString); + SetIsOnlyLowChars(onlyLow); + }; + inline ULONG GetCharCount() const + { + LIMITED_METHOD_CONTRACT; + + _ASSERTE ((cch & ~ONLY_LOW_CHARS_MASK) == dwDebugCch); + return (cch & ~ONLY_LOW_CHARS_MASK); + } + inline void SetCharCount(ULONG _cch) + { + LIMITED_METHOD_CONTRACT; + +#ifdef _DEBUG + dwDebugCch = _cch; +#endif // _DEBUG + cch = ((DWORD)_cch) | (cch & ONLY_LOW_CHARS_MASK); + } + inline LPCWSTR GetStringBuffer() const + { + LIMITED_METHOD_CONTRACT; + + return (szString); + } + inline void SetStringBuffer(LPCWSTR _szString) + { + LIMITED_METHOD_CONTRACT; + + szString = _szString; + } + inline BOOL GetIsOnlyLowChars() const + { + LIMITED_METHOD_CONTRACT; + + _ASSERTE(bDebugOnlyLowChars == ((cch & ONLY_LOW_CHARS_MASK) ? TRUE : FALSE)); + return ((cch & ONLY_LOW_CHARS_MASK) ? TRUE : FALSE); + } + inline void SetIsOnlyLowChars(BOOL bIsOnlyLowChars) + { + LIMITED_METHOD_CONTRACT; + +#ifdef _DEBUG + bDebugOnlyLowChars = bIsOnlyLowChars; +#endif // _DEBUG + bIsOnlyLowChars ? (cch |= ONLY_LOW_CHARS_MASK) : (cch &= ~ONLY_LOW_CHARS_MASK); + } +}; + +class EEUnicodeHashTableHelper +{ +public: + static EEHashEntry_t * AllocateEntry(EEStringData *pKey, BOOL bDeepCopy, AllocationHeap Heap); + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap); + static BOOL CompareKeys(EEHashEntry_t *pEntry, EEStringData *pKey); + static DWORD Hash(EEStringData *pKey); + static EEStringData * GetKey(EEHashEntry_t *pEntry); + static void ReplaceKey(EEHashEntry_t *pEntry, EEStringData *pNewKey); +}; + +typedef EEHashTable<EEStringData *, EEUnicodeHashTableHelper, TRUE> EEUnicodeStringHashTable; + + +class EEUnicodeStringLiteralHashTableHelper +{ +public: + static EEHashEntry_t * AllocateEntry(EEStringData *pKey, BOOL bDeepCopy, AllocationHeap Heap); + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap); + static BOOL CompareKeys(EEHashEntry_t *pEntry, EEStringData *pKey); + static DWORD Hash(EEStringData *pKey); + static void ReplaceKey(EEHashEntry_t *pEntry, EEStringData *pNewKey); +}; + +typedef EEHashTable<EEStringData *, EEUnicodeStringLiteralHashTableHelper, TRUE> EEUnicodeStringLiteralHashTable; + +// Permission set hash table. + +class EEPsetHashTableHelper +{ +public: + static EEHashEntry_t * AllocateEntry(PsetCacheKey *pKey, BOOL bDeepCopy, AllocationHeap Heap); + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap); + static BOOL CompareKeys(EEHashEntry_t *pEntry, PsetCacheKey *pKey); + static DWORD Hash(PsetCacheKey *pKey); + static PsetCacheKey *GetKey(EEHashEntry_t *pEntry); +}; + +typedef EEHashTable<PsetCacheKey *, EEPsetHashTableHelper, FALSE> EEPsetHashTable; + + +// Generic pointer hash table helper. + +template <class KeyPointerType> +class EEPtrHashTableHelper +{ +public: + static EEHashEntry_t *AllocateEntry(KeyPointerType pKey, BOOL bDeepCopy, AllocationHeap Heap) + { + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(return FALSE;); + } + CONTRACTL_END + + _ASSERTE(!bDeepCopy && "Deep copy is not supported by the EEPtrHashTableHelper"); + _ASSERTE(sizeof(KeyPointerType) == sizeof(void *) && "KeyPointerType must be a pointer type"); + + EEHashEntry_t *pEntry = (EEHashEntry_t *) new (nothrow) BYTE[SIZEOF_EEHASH_ENTRY + sizeof(KeyPointerType)]; + if (!pEntry) + return NULL; + *((KeyPointerType*)pEntry->Key) = pKey; + + return pEntry; + } + + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap) + { + LIMITED_METHOD_CONTRACT; + + // Delete the entry. + delete [] (BYTE*) pEntry; + } + + static BOOL CompareKeys(EEHashEntry_t *pEntry, KeyPointerType pKey) + { + LIMITED_METHOD_CONTRACT; + SUPPORTS_DAC; + + KeyPointerType pEntryKey = *((KeyPointerType*)pEntry->Key); + return pEntryKey == pKey; + } + + static DWORD Hash(KeyPointerType pKey) + { + LIMITED_METHOD_CONTRACT; + SUPPORTS_DAC; + +#ifdef _TARGET_X86_ + return (DWORD)(size_t) dac_cast<TADDR>(pKey); +#else + // <TODO> IA64: Is this a good hashing mechanism on IA64?</TODO> + return (DWORD)(((size_t) dac_cast<TADDR>(pKey)) >> 3); +#endif + } + + static KeyPointerType GetKey(EEHashEntry_t *pEntry) + { + LIMITED_METHOD_CONTRACT; + + return *((KeyPointerType*)pEntry->Key); + } +}; + +typedef EEHashTable<PTR_VOID, EEPtrHashTableHelper<PTR_VOID>, FALSE> EEPtrHashTable; +typedef DPTR(EEPtrHashTable) PTR_EEPtrHashTable; + +// Define a hash of generic instantiations (represented by a SigTypeContext). +class EEInstantiationHashTableHelper +{ +public: + static EEHashEntry_t *AllocateEntry(const SigTypeContext *pKey, BOOL bDeepCopy, AllocationHeap pHeap = 0); + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap pHeap = 0); + static BOOL CompareKeys(EEHashEntry_t *pEntry, const SigTypeContext *pKey); + static DWORD Hash(const SigTypeContext *pKey); + static const SigTypeContext *GetKey(EEHashEntry_t *pEntry); +}; +typedef EEHashTable<const SigTypeContext*, EEInstantiationHashTableHelper, FALSE> EEInstantiationHashTable; + +// ComComponentInfo hashtable. + +struct ClassFactoryInfo +{ + GUID m_clsid; + WCHAR *m_strServerName; +}; + +class EEClassFactoryInfoHashTableHelper +{ +public: + static EEHashEntry_t *AllocateEntry(ClassFactoryInfo *pKey, BOOL bDeepCopy, AllocationHeap Heap); + static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap); + static BOOL CompareKeys(EEHashEntry_t *pEntry, ClassFactoryInfo *pKey); + static DWORD Hash(ClassFactoryInfo *pKey); + static ClassFactoryInfo *GetKey(EEHashEntry_t *pEntry); +}; + +typedef EEHashTable<ClassFactoryInfo *, EEClassFactoryInfoHashTableHelper, TRUE> EEClassFactoryInfoHashTable; +// Struct to hold a client's iteration state +struct EEHashTableIteration +{ + DWORD m_dwBucket; + EEHashEntry_t *m_pEntry; + +#ifdef _DEBUG + void *m_pTable; +#endif +}; + +#endif /* _EE_HASH_H */ |