diff options
Diffstat (limited to 'src/vm/eehash.inl')
-rw-r--r-- | src/vm/eehash.inl | 877 |
1 files changed, 877 insertions, 0 deletions
diff --git a/src/vm/eehash.inl b/src/vm/eehash.inl new file mode 100644 index 0000000000..ba25fcbee5 --- /dev/null +++ b/src/vm/eehash.inl @@ -0,0 +1,877 @@ +// 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 _EE_HASH_INL +#define _EE_HASH_INL + +#ifdef _DEBUG_IMPL +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::OwnLock() +{ + WRAPPER_NO_CONTRACT; + if (m_CheckThreadSafety == FALSE) + return TRUE; + + if (m_pfnLockOwner == NULL) { + return m_writerThreadId.IsCurrentThread(); + } + else { + BOOL ret = m_pfnLockOwner(m_lockData); + if (!ret) { + if (Debug_IsLockedViaThreadSuspension()) { + ret = TRUE; + } + } + return ret; + } +} +#endif // _DEBUG_IMPL + +#ifndef DACCESS_COMPILE +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::Destroy() +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + if (m_pVolatileBucketTable && m_pVolatileBucketTable->m_pBuckets != NULL) + { + DWORD i; + + for (i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++) + { + EEHashEntry_t *pEntry, *pNext; + + for (pEntry = m_pVolatileBucketTable->m_pBuckets[i]; pEntry != NULL; pEntry = pNext) + { + pNext = pEntry->pNext; + Helper::DeleteEntry(pEntry, m_Heap); + } + } + + delete[] (m_pVolatileBucketTable->m_pBuckets-1); + + m_pVolatileBucketTable = NULL; + } + +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::ClearHashTable() +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + //_ASSERTE (OwnLock()); + + // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read + // from multiple threads without taking locks. On rehash, you want to get rid of the old copy + // of table. You can only get rid of it once nobody is using it. That's a problem because + // there is no lock to tell when the last reader stopped using the old copy of the table. + // The solution to this problem is to access the table in cooperative mode, and to get rid of + // the old copy of the table when we are suspended for GC. When we are suspended for GC, + // we know that nobody is using the old copy of the table anymore. + // BROKEN: This is called sometimes from the CorMap hash before the EE is started up + GCX_COOP_NO_THREAD_BROKEN(); + + if (m_pVolatileBucketTable->m_pBuckets != NULL) + { + DWORD i; + + for (i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++) + { + EEHashEntry_t *pEntry, *pNext; + + for (pEntry = m_pVolatileBucketTable->m_pBuckets[i]; pEntry != NULL; pEntry = pNext) + { + pNext = pEntry->pNext; + Helper::DeleteEntry(pEntry, m_Heap); + } + } + + delete[] (m_pVolatileBucketTable->m_pBuckets-1); + m_pVolatileBucketTable->m_pBuckets = NULL; + } + + m_pVolatileBucketTable->m_dwNumBuckets = 0; + m_dwNumEntries = 0; +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::EmptyHashTable() +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE (OwnLock()); + + // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read + // from multiple threads without taking locks. On rehash, you want to get rid of the old copy + // of table. You can only get rid of it once nobody is using it. That's a problem because + // there is no lock to tell when the last reader stopped using the old copy of the table. + // The solution to this problem is to access the table in cooperative mode, and to get rid of + // the old copy of the table when we are suspended for GC. When we are suspended for GC, + // we know that nobody is using the old copy of the table anymore. + // BROKEN: This is called sometimes from the CorMap hash before the EE is started up + GCX_COOP_NO_THREAD_BROKEN(); + + if (m_pVolatileBucketTable->m_pBuckets != NULL) + { + DWORD i; + + for (i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++) + { + EEHashEntry_t *pEntry, *pNext; + + for (pEntry = m_pVolatileBucketTable->m_pBuckets[i]; pEntry != NULL; pEntry = pNext) + { + pNext = pEntry->pNext; + Helper::DeleteEntry(pEntry, m_Heap); + } + + m_pVolatileBucketTable->m_pBuckets[i] = NULL; + } + } + + m_dwNumEntries = 0; +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> + +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::Init(DWORD dwNumBuckets, LockOwner *pLock, AllocationHeap pHeap, BOOL CheckThreadSafety) +{ + CONTRACTL + { + WRAPPER(NOTHROW); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(return FALSE;); + +#ifndef DACCESS_COMPILE + PRECONDITION(m_pVolatileBucketTable.Load() == NULL && "EEHashTable::Init() called twice."); +#endif + + } + CONTRACTL_END + + m_pVolatileBucketTable = &m_BucketTable[0]; + + DWORD dwNumBucketsPlusOne; + + // Prefast overflow sanity check the addition + if (!ClrSafeInt<DWORD>::addition(dwNumBuckets, 1, dwNumBucketsPlusOne)) + return FALSE; + + S_SIZE_T safeSize(sizeof(EEHashEntry_t *)); + safeSize *= dwNumBucketsPlusOne; + if (safeSize.IsOverflow()) + ThrowHR(COR_E_OVERFLOW); + SIZE_T cbAlloc = safeSize.Value(); + + m_pVolatileBucketTable->m_pBuckets = (EEHashEntry_t **) new (nothrow) BYTE[cbAlloc]; + + if (m_pVolatileBucketTable->m_pBuckets == NULL) + return FALSE; + + memset(m_pVolatileBucketTable->m_pBuckets, 0, cbAlloc); + + // The first slot links to the next list. + m_pVolatileBucketTable->m_pBuckets++; + + m_pVolatileBucketTable->m_dwNumBuckets = dwNumBuckets; + + m_Heap = pHeap; + +#ifdef _DEBUG + if (pLock == NULL) { + m_lockData = NULL; + m_pfnLockOwner = NULL; + } + else { + m_lockData = pLock->lock; + m_pfnLockOwner = pLock->lockOwnerFunc; + } + + if (m_pfnLockOwner == NULL) { + m_writerThreadId.SetToCurrentThread(); + } + m_CheckThreadSafety = CheckThreadSafety; +#endif + + return TRUE; +} + + +// Does not handle duplicates! + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::InsertValue(KeyType pKey, HashDatum Data, BOOL bDeepCopyKey) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(COMPlusThrowOM();); + } + CONTRACTL_END + + _ASSERTE (OwnLock()); + + // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read + // from multiple threads without taking locks. On rehash, you want to get rid of the old copy + // of table. You can only get rid of it once nobody is using it. That's a problem because + // there is no lock to tell when the last reader stopped using the old copy of the table. + // The solution to this problem is to access the table in cooperative mode, and to get rid of + // the old copy of the table when we are suspended for GC. When we are suspended for GC, + // we know that nobody is using the old copy of the table anymore. + // BROKEN: This is called sometimes from the CorMap hash before the EE is started up + GCX_COOP_NO_THREAD_BROKEN(); + + _ASSERTE(m_pVolatileBucketTable->m_dwNumBuckets != 0); + + if (m_dwNumEntries > m_pVolatileBucketTable->m_dwNumBuckets*2) + { + if (!GrowHashTable()) COMPlusThrowOM(); + } + + DWORD dwHash = (DWORD)Helper::Hash(pKey); + DWORD dwBucket = dwHash % m_pVolatileBucketTable->m_dwNumBuckets; + EEHashEntry_t * pNewEntry; + + pNewEntry = Helper::AllocateEntry(pKey, bDeepCopyKey, m_Heap); + if (!pNewEntry) + { + COMPlusThrowOM(); + } + + // Fill in the information for the new entry. + pNewEntry->pNext = m_pVolatileBucketTable->m_pBuckets[dwBucket]; + pNewEntry->Data = Data; + pNewEntry->dwHashValue = dwHash; + + // Insert at head of bucket + // need volatile write to avoid write reordering problem in IA + VolatileStore(&m_pVolatileBucketTable->m_pBuckets[dwBucket], pNewEntry);; + + m_dwNumEntries++; +} + + +// Similar to the above, except that the HashDatum is a pointer to key. +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::InsertKeyAsValue(KeyType pKey, BOOL bDeepCopyKey) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(COMPlusThrowOM();); + } + CONTRACTL_END + + _ASSERTE (OwnLock()); + + // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read + // from multiple threads without taking locks. On rehash, you want to get rid of the old copy + // of table. You can only get rid of it once nobody is using it. That's a problem because + // there is no lock to tell when the last reader stopped using the old copy of the table. + // The solution to this problem is to access the table in cooperative mode, and to get rid of + // the old copy of the table when we are suspended for GC. When we are suspended for GC, + // we know that nobody is using the old copy of the table anymore. + // BROKEN: This is called sometimes from the CorMap hash before the EE is started up + GCX_COOP_NO_THREAD_BROKEN(); + + _ASSERTE(m_pVolatileBucketTable->m_dwNumBuckets != 0); + + if (m_dwNumEntries > m_pVolatileBucketTable->m_dwNumBuckets*2) + { + if (!GrowHashTable()) COMPlusThrowOM(); + } + + DWORD dwHash = Helper::Hash(pKey); + DWORD dwBucket = dwHash % m_pVolatileBucketTable->m_dwNumBuckets; + EEHashEntry_t * pNewEntry; + + pNewEntry = Helper::AllocateEntry(pKey, bDeepCopyKey, m_Heap); + if (!pNewEntry) + { + COMPlusThrowOM(); + } + + // Fill in the information for the new entry. + pNewEntry->pNext = m_pVolatileBucketTable->m_pBuckets[dwBucket]; + pNewEntry->dwHashValue = dwHash; + pNewEntry->Data = *((LPUTF8 *)pNewEntry->Key); + + // Insert at head of bucket + // need volatile write to avoid write reordering problem in IA + VolatileStore(&m_pVolatileBucketTable->m_pBuckets[dwBucket], pNewEntry); + + m_dwNumEntries++; +} + + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::DeleteValue(KeyType pKey) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE (OwnLock()); + + Thread *pThread = GetThreadNULLOk(); + GCX_MAYBE_COOP_NO_THREAD_BROKEN(pThread ? !(pThread->m_StateNC & Thread::TSNC_UnsafeSkipEnterCooperative) : FALSE); + + _ASSERTE(m_pVolatileBucketTable->m_dwNumBuckets != 0); + + DWORD dwHash = Helper::Hash(pKey); + DWORD dwBucket = dwHash % m_pVolatileBucketTable->m_dwNumBuckets; + EEHashEntry_t * pSearch; + EEHashEntry_t **ppPrev = &m_pVolatileBucketTable->m_pBuckets[dwBucket]; + + for (pSearch = m_pVolatileBucketTable->m_pBuckets[dwBucket]; pSearch; pSearch = pSearch->pNext) + { + if (pSearch->dwHashValue == dwHash && Helper::CompareKeys(pSearch, pKey)) + { + *ppPrev = pSearch->pNext; + Helper::DeleteEntry(pSearch, m_Heap); + + // Do we ever want to shrink? + m_dwNumEntries--; + + return TRUE; + } + + ppPrev = &pSearch->pNext; + } + + return FALSE; +} + + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::ReplaceValue(KeyType pKey, HashDatum Data) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE (OwnLock()); + + EEHashEntry_t *pItem = FindItem(pKey); + + if (pItem != NULL) + { + // Required to be atomic + pItem->Data = Data; + return TRUE; + } + else + { + return FALSE; + } +} + + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::ReplaceKey(KeyType pOldKey, KeyType pNewKey) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE (OwnLock()); + + EEHashEntry_t *pItem = FindItem(pOldKey); + + if (pItem != NULL) + { + Helper::ReplaceKey (pItem, pNewKey); + return TRUE; + } + else + { + return FALSE; + } +} +#endif // !DACCESS_COMPILE + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +DWORD EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetHash(KeyType pKey) +{ + WRAPPER_NO_CONTRACT; + return Helper::Hash(pKey); +} + + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetValue(KeyType pKey, HashDatum *pData) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + SO_TOLERANT; + SUPPORTS_DAC; + } + CONTRACTL_END + + EEHashEntry_t *pItem = FindItem(pKey); + + if (pItem != NULL) + { + *pData = pItem->Data; + return TRUE; + } + else + { + return FALSE; + } +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetValue(KeyType pKey, HashDatum *pData, DWORD hashValue) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + EEHashEntry_t *pItem = FindItem(pKey, hashValue); + + if (pItem != NULL) + { + *pData = pItem->Data; + return TRUE; + } + else + { + return FALSE; + } +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +FORCEINLINE BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetValueSpeculative(KeyType pKey, HashDatum *pData) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); +#ifdef MODE_COOPERATIVE // This header file sees contract.h, not eecontract.h - what a kludge! + MODE_COOPERATIVE; +#endif + SO_TOLERANT; + } + CONTRACTL_END + + EEHashEntry_t *pItem = FindItemSpeculative(pKey, Helper::Hash(pKey)); + + if (pItem != NULL) + { + *pData = pItem->Data; + return TRUE; + } + else + { + return FALSE; + } +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +EEHashEntry_t *EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::FindItem(KeyType pKey) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + SO_TOLERANT; + SUPPORTS_DAC; + } + CONTRACTL_END + + return FindItem(pKey, Helper::Hash(pKey)); +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +EEHashEntry_t *EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::FindItem(KeyType pKey, DWORD dwHash) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + SO_TOLERANT; + SUPPORTS_DAC; + } + CONTRACTL_END + + // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read + // from multiple threads without taking locks. On rehash, you want to get rid of the old copy + // of table. You can only get rid of it once nobody is using it. That's a problem because + // there is no lock to tell when the last reader stopped using the old copy of the table. + // The solution to this problem is to access the table in cooperative mode, and to get rid of + // the old copy of the table when we are suspended for GC. When we are suspended for GC, + // we know that nobody is using the old copy of the table anymore. + // +#ifndef DACCESS_COMPILE + GCX_COOP_NO_THREAD_BROKEN(); +#endif + + // Atomic transaction. In any other point of this method or ANY of the callees of this function you can not read + // from m_pVolatileBucketTable!!!!!!! A racing condition would occur. + DWORD dwOldNumBuckets; + +#ifndef DACCESS_COMPILE + DWORD nTry = 0; + DWORD dwSwitchCount = 0; +#endif + + do + { + BucketTable* pBucketTable=(BucketTable*)(PTR_BucketTable)m_pVolatileBucketTable.Load(); + dwOldNumBuckets = pBucketTable->m_dwNumBuckets; + + _ASSERTE(pBucketTable->m_dwNumBuckets != 0); + + DWORD dwBucket = dwHash % pBucketTable->m_dwNumBuckets; + EEHashEntry_t * pSearch; + + for (pSearch = pBucketTable->m_pBuckets[dwBucket]; pSearch; pSearch = pSearch->pNext) + { + if (pSearch->dwHashValue == dwHash && Helper::CompareKeys(pSearch, pKey)) + return pSearch; + } + + // There is a race in EEHash Table: when we grow the hash table, we will nuke out + // the old bucket table. Readers might be looking up in the old table, they can + // fail to find an existing entry. The workaround is to retry the search process + // if we are called grow table during the search process. +#ifndef DACCESS_COMPILE + nTry ++; + if (nTry == 20) { + __SwitchToThread(0, ++dwSwitchCount); + nTry = 0; + } +#endif // #ifndef DACCESS_COMPILE + } + while ( m_bGrowing || dwOldNumBuckets != m_pVolatileBucketTable->m_dwNumBuckets); + + return NULL; +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +FORCEINLINE EEHashEntry_t *EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::FindItemSpeculative(KeyType pKey, DWORD dwHash) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); +#ifdef MODE_COOPERATIVE // This header file sees contract.h, not eecontract.h - what a kludge! + MODE_COOPERATIVE; +#endif + SO_TOLERANT; + } + CONTRACTL_END + + // Atomic transaction. In any other point of this method or ANY of the callees of this function you can not read + // from m_pVolatileBucketTable!!!!!!! A racing condition would occur. + DWORD dwOldNumBuckets; + + BucketTable* pBucketTable=m_pVolatileBucketTable; + dwOldNumBuckets = pBucketTable->m_dwNumBuckets; + + _ASSERTE(pBucketTable->m_dwNumBuckets != 0); + + DWORD dwBucket = dwHash % pBucketTable->m_dwNumBuckets; + EEHashEntry_t * pSearch; + + for (pSearch = pBucketTable->m_pBuckets[dwBucket]; pSearch; pSearch = pSearch->pNext) + { + if (pSearch->dwHashValue == dwHash && Helper::CompareKeys(pSearch, pKey)) + return pSearch; + } + + return NULL; +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::IsEmpty() +{ + LIMITED_METHOD_CONTRACT; + return m_dwNumEntries == 0; +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +DWORD EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetCount() +{ + LIMITED_METHOD_CONTRACT; + return m_dwNumEntries; +} + +#ifndef DACCESS_COMPILE + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GrowHashTable() +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + INJECT_FAULT(return FALSE;); + } + CONTRACTL_END + +#if defined(_DEBUG) && !defined(CROSSGEN_COMPILE) + BEGIN_GETTHREAD_ALLOWED; + Thread * pThread = GetThread(); + _ASSERTE(!g_fEEStarted || (pThread == NULL) || (pThread->PreemptiveGCDisabled())); + END_GETTHREAD_ALLOWED; +#endif + + // Make the new bucket table 4 times bigger + // + DWORD dwNewNumBuckets; + DWORD dwNewNumBucketsPlusOne; + { + S_UINT32 safeSize(m_pVolatileBucketTable->m_dwNumBuckets); + + safeSize *= 4; + + if (safeSize.IsOverflow()) + return FALSE; + + dwNewNumBuckets = safeSize.Value(); + + safeSize += 1; // Allocate one extra + + if (safeSize.IsOverflow()) + return FALSE; + + dwNewNumBucketsPlusOne = safeSize.Value(); + } + + // On resizes, we still have an array of old pointers we need to worry about. + // We can't free these old pointers, for we may hit a race condition where we're + // resizing and reading from the array at the same time. We need to keep track of these + // old arrays of pointers, so we're going to use the last item in the array to "link" + // to previous arrays, so that they may be freed at the end. + // + + SIZE_T cbAlloc; + { + S_SIZE_T safeSize(sizeof(EEHashEntry_t *)); + + safeSize *= dwNewNumBucketsPlusOne; + + if (safeSize.IsOverflow()) + return FALSE; + + cbAlloc = safeSize.Value(); + } + + EEHashEntry_t **pNewBuckets = (EEHashEntry_t **) new (nothrow) BYTE[cbAlloc]; + + if (pNewBuckets == NULL) + return FALSE; + + memset(pNewBuckets, 0, cbAlloc); + + // The first slot is linked to next list. + pNewBuckets++; + + // Run through the old table and transfer all the entries + + // Be sure not to mess with the integrity of the old table while + // we are doing this, as there can be concurrent readers! Note that + // it is OK if the concurrent reader misses out on a match, though - + // they will have to acquire the lock on a miss & try again. + FastInterlockExchange( (LONG *) &m_bGrowing, 1); + for (DWORD i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++) + { + EEHashEntry_t * pEntry = m_pVolatileBucketTable->m_pBuckets[i]; + + // Try to lock out readers from scanning this bucket. This is + // obviously a race which may fail. However, note that it's OK + // if somebody is already in the list - it's OK if we mess + // with the bucket groups, as long as we don't destroy + // anything. The lookup function will still do appropriate + // comparison even if it wanders aimlessly amongst entries + // while we are rearranging things. If a lookup finds a match + // under those circumstances, great. If not, they will have + // to acquire the lock & try again anyway. + + m_pVolatileBucketTable->m_pBuckets[i] = NULL; + + while (pEntry != NULL) + { + DWORD dwNewBucket = pEntry->dwHashValue % dwNewNumBuckets; + EEHashEntry_t * pNextEntry = pEntry->pNext; + + pEntry->pNext = pNewBuckets[dwNewBucket]; + pNewBuckets[dwNewBucket] = pEntry; + pEntry = pNextEntry; + } + } + + + // Finally, store the new number of buckets and the new bucket table + BucketTable* pNewBucketTable = (m_pVolatileBucketTable == &m_BucketTable[0]) ? + &m_BucketTable[1]: + &m_BucketTable[0]; + + pNewBucketTable->m_pBuckets = pNewBuckets; + pNewBucketTable->m_dwNumBuckets = dwNewNumBuckets; + + // Add old table to the to free list. Note that the SyncClean thing will only + // delete the buckets at a safe point + // + SyncClean::AddEEHashTable (m_pVolatileBucketTable->m_pBuckets); + + // Note that the SyncClean:AddEEHashTable performs at least one Interlock operation + // So we do not need to use an Interlocked operation to write m_pVolatileBucketTable + // Swap the double buffer, this is an atomic operation (the assignment) + // + m_pVolatileBucketTable = pNewBucketTable; + + FastInterlockExchange( (LONG *) &m_bGrowing, 0); + + return TRUE; +} + +#endif // DACCESS_COMPILE + +// Walk through all the entries in the hash table, in meaningless order, without any +// synchronization. +// +// IterateStart() +// while (IterateNext()) +// GetKey(); +// +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>:: + IterateStart(EEHashTableIteration *pIter) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE_IMPL(OwnLock()); + pIter->m_dwBucket = -1; + pIter->m_pEntry = NULL; + +#ifdef _DEBUG + pIter->m_pTable = this; +#endif +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>:: + IterateNext(EEHashTableIteration *pIter) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE_IMPL(OwnLock()); + + Thread *pThread = GetThreadNULLOk(); + GCX_MAYBE_COOP_NO_THREAD_BROKEN(pThread ? !(pThread->m_StateNC & Thread::TSNC_UnsafeSkipEnterCooperative) : FALSE); + + _ASSERTE(pIter->m_pTable == (void *) this); + + // If we haven't started iterating yet, or if we are at the end of a particular + // chain, advance to the next chain. + while (pIter->m_pEntry == NULL || pIter->m_pEntry->pNext == NULL) + { + if (++pIter->m_dwBucket >= m_pVolatileBucketTable->m_dwNumBuckets) + { + // advanced beyond the end of the table. + _ASSERTE(pIter->m_dwBucket == m_pVolatileBucketTable->m_dwNumBuckets); // client keeps asking? + return FALSE; + } + pIter->m_pEntry = m_pVolatileBucketTable->m_pBuckets[pIter->m_dwBucket]; + + // If this bucket has no chain, keep advancing. Otherwise we are done + if (pIter->m_pEntry) + return TRUE; + } + + // We are within a chain. Advance to the next entry + pIter->m_pEntry = pIter->m_pEntry->pNext; + + _ASSERTE(pIter->m_pEntry); + return TRUE; +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +KeyType EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>:: + IterateGetKey(EEHashTableIteration *pIter) +{ + CONTRACTL + { + WRAPPER(THROWS); + WRAPPER(GC_NOTRIGGER); + FORBID_FAULT; + } + CONTRACTL_END + + _ASSERTE(pIter->m_pTable == (void *) this); + _ASSERTE(pIter->m_dwBucket < m_pVolatileBucketTable->m_dwNumBuckets && pIter->m_pEntry); + return Helper::GetKey(pIter->m_pEntry); +} + +template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep> +HashDatum EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>:: + IterateGetValue(EEHashTableIteration *pIter) +{ + LIMITED_METHOD_CONTRACT; + + _ASSERTE(pIter->m_pTable == (void *) this); + _ASSERTE(pIter->m_dwBucket < m_pVolatileBucketTable->m_dwNumBuckets && pIter->m_pEntry); + return pIter->m_pEntry->Data; +} + +#endif /* _EE_HASH_INL */ |