diff options
Diffstat (limited to 'src/vm/hash.cpp')
| -rw-r--r-- | src/vm/hash.cpp | 1234 |
1 files changed, 1234 insertions, 0 deletions
diff --git a/src/vm/hash.cpp b/src/vm/hash.cpp new file mode 100644 index 0000000000..205f736b0d --- /dev/null +++ b/src/vm/hash.cpp @@ -0,0 +1,1234 @@ +// 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. + + +/*++ + +Module Name: + + synchash.cpp + +--*/ + +#include "common.h" + +#include "hash.h" + +#include "excep.h" + +#include "syncclean.hpp" + +#include "threadsuspend.h" + +//--------------------------------------------------------------------- +// Array of primes, used by hash table to choose the number of buckets +// Review: would we want larger primes? e.g., for 64-bit? + +const DWORD g_rgPrimes[] = { +5,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919, +1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591, +17519,21023,25229,30293,36353,43627,52361,62851,75431,90523, 108631, 130363, +156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, +968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, +4999559, 5999471, 7199369 +}; +const SIZE_T g_rgNumPrimes = sizeof(g_rgPrimes) / sizeof(*g_rgPrimes); + +const unsigned int SLOTS_PER_BUCKET = 4; + +#ifndef DACCESS_COMPILE + +void *PtrHashMap::operator new(size_t size, LoaderHeap *pHeap) +{ + STATIC_CONTRACT_THROWS; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FAULT; //return NULL; + + return pHeap->AllocMem(S_SIZE_T(size)); +} + +void PtrHashMap::operator delete(void *p) +{ +} + + +//----------------------------------------------------------------- +// Bucket methods + +BOOL Bucket::InsertValue(const UPTR key, const UPTR value) +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FAULT; //return FALSE; + + _ASSERTE(key != EMPTY); + _ASSERTE(key != DELETED); + + if (!HasFreeSlots()) + return false; //no free slots + + // might have a free slot + for (UPTR i = 0; i < SLOTS_PER_BUCKET; i++) + { + //@NOTE we can't reuse DELETED slots + if (m_rgKeys[i] == EMPTY) + { + SetValue (value, i); + + // On multiprocessors we should make sure that + // the value is propagated before we proceed. + // inline memory barrier call, refer to + // function description at the beginning of this + MemoryBarrier(); + + m_rgKeys[i] = key; + return true; + } + } // for i= 0; i < SLOTS_PER_BUCKET; loop + + SetCollision(); // otherwise set the collision bit + return false; +} + +#endif // !DACCESS_COMPILE + +//--------------------------------------------------------------------- +// inline Bucket* HashMap::Buckets() +// get the pointer to the bucket array +inline +PTR_Bucket HashMap::Buckets() +{ + LIMITED_METHOD_DAC_CONTRACT; + +#if !defined(DACCESS_COMPILE) && !defined(CROSSGEN_COMPILE) + _ASSERTE (!g_fEEStarted || !m_fAsyncMode || GetThread() == NULL || GetThread()->PreemptiveGCDisabled() || IsGCThread()); +#endif + return m_rgBuckets + 1; +} + +//--------------------------------------------------------------------- +// inline size_t HashMap::GetSize(PTR_Bucket rgBuckets) +// get the number of buckets +inline +DWORD HashMap::GetSize(PTR_Bucket rgBuckets) +{ + LIMITED_METHOD_DAC_CONTRACT; + PTR_size_t pSize = dac_cast<PTR_size_t>(rgBuckets - 1); + _ASSERTE(FitsIn<DWORD>(pSize[0])); + return static_cast<DWORD>(pSize[0]); +} + + +//--------------------------------------------------------------------- +// inline size_t HashMap::HashFunction(UPTR key, UINT numBuckets, UINT &seed, UINT &incr) +// get the first & second hash function. +// H(key, i) = h1(key) + i*h2(key, hashSize); 0 <= i < numBuckets +// h2 must return a value >= 1 and < numBuckets. +inline +void HashMap::HashFunction(const UPTR key, const UINT numBuckets, UINT &seed, UINT &incr) +{ + LIMITED_METHOD_CONTRACT; + // First hash function + // We commonly use pointers, which are 4 byte aligned, so the two least + // significant bits are often 0, then we mod this value by something like + // 11. We can get a better distribution for pointers by dividing by 4. + // REVIEW: Is 64-bit truncation better or should we be doing something with the + // upper 32-bits in either of these hash functions. + seed = static_cast<UINT>(key >> 2); + // Second hash function + incr = (UINT)(1 + (((static_cast<UINT>(key >> 5)) + 1) % ((UINT)numBuckets - 1))); + _ASSERTE(incr > 0 && incr < numBuckets); +} + +#ifndef DACCESS_COMPILE + +//--------------------------------------------------------------------- +// inline void HashMap::SetSize(Bucket *rgBuckets, size_t size) +// set the number of buckets +inline +void HashMap::SetSize(Bucket *rgBuckets, size_t size) +{ + LIMITED_METHOD_CONTRACT; + ((size_t*)rgBuckets)[0] = size; +} + +//--------------------------------------------------------------------- +// HashMap::HashMap() +// constructor, initialize all values +// +HashMap::HashMap() +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + m_rgBuckets = NULL; + m_pCompare = NULL; // comparsion object + m_cbInserts = 0; // track inserts + m_cbDeletes = 0; // track deletes + m_cbPrevSlotsInUse = 0; // track valid slots present during previous rehash + + //Debug data member +#ifdef _DEBUG + m_fInSyncCode = false; +#endif + // profile data members +#ifdef HASHTABLE_PROFILE + m_cbRehash = 0; + m_cbRehashSlots = 0; + m_cbObsoleteTables = 0; + m_cbTotalBuckets =0; + m_cbInsertProbesGt8 = 0; // inserts that needed more than 8 probes + maxFailureProbe =0; + memset(m_rgLookupProbes,0,HASHTABLE_LOOKUP_PROBES_DATA*sizeof(LONG)); +#endif // HASHTABLE_PROFILE +#ifdef _DEBUG + m_lockData = NULL; + m_pfnLockOwner = NULL; +#endif // _DEBUG +} + +//--------------------------------------------------------------------- +// void HashMap::Init(unsigned cbInitialSize, CompareFnPtr ptr, bool fAsyncMode) +// set the initial size of the hash table and provide the comparison +// function pointer +// +void HashMap::Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock) +{ + CONTRACTL + { + THROWS; + GC_NOTRIGGER; + INJECT_FAULT(COMPlusThrowOM()); + } + CONTRACTL_END + + Compare* pCompare = NULL; + if (ptr != NULL) + { + pCompare = new Compare(ptr); + } + Init(cbInitialSize, pCompare, fAsyncMode, pLock); +} + +DWORD HashMap::GetNearestIndex(DWORD cbInitialSize) +{ + LIMITED_METHOD_CONTRACT; + + DWORD lowIndex = 0; + DWORD highIndex = g_rgNumPrimes - 1; + DWORD midIndex = (highIndex + 1) / 2; + + if (cbInitialSize <= g_rgPrimes[0]) + return 0; + + if (cbInitialSize >= g_rgPrimes[highIndex]) + return highIndex; + + while (true) + { + if (cbInitialSize < g_rgPrimes[midIndex]) + { + highIndex = midIndex; + } + else + { + if (cbInitialSize == g_rgPrimes[midIndex]) + return midIndex; + lowIndex = midIndex; + } + midIndex = lowIndex + (highIndex - lowIndex + 1)/2; + if (highIndex == midIndex) + { + _ASSERTE(g_rgPrimes[highIndex] >= cbInitialSize); + _ASSERTE(highIndex < g_rgNumPrimes); + return highIndex; + } + } +} + +//--------------------------------------------------------------------- +// void HashMap::Init(unsigned cbInitialSize, Compare* pCompare, bool fAsyncMode) +// set the initial size of the hash table and provide the comparison +// function pointer +// +void HashMap::Init(DWORD cbInitialSize, Compare* pCompare, BOOL fAsyncMode, LockOwner *pLock) +{ + CONTRACTL + { + THROWS; + GC_NOTRIGGER; + INJECT_FAULT(COMPlusThrowOM()); + } + CONTRACTL_END + + m_iPrimeIndex = GetNearestIndex(cbInitialSize); + DWORD size = g_rgPrimes[m_iPrimeIndex]; + PREFIX_ASSUME(size < 0x7fffffff); + + m_rgBuckets = new Bucket[size+1]; + + memset (m_rgBuckets, 0, (size+1)*sizeof(Bucket)); + SetSize(m_rgBuckets, size); + + m_pCompare = pCompare; + + m_fAsyncMode = fAsyncMode != FALSE; + + // assert null comparison returns true + //ASSERT( + // m_pCompare == NULL || + // (m_pCompare->CompareHelper(0,0) != 0) + // ); + +#ifdef HASHTABLE_PROFILE + m_cbTotalBuckets = size+1; +#endif + +#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(); + } +#endif // _DEBUG +} + +//--------------------------------------------------------------------- +// void PtrHashMap::Init(unsigned cbInitialSize, CompareFnPtr ptr, bool fAsyncMode) +// set the initial size of the hash table and provide the comparison +// function pointer +// +void PtrHashMap::Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock) +{ + CONTRACTL + { + THROWS; + GC_NOTRIGGER; + INJECT_FAULT(COMPlusThrowOM()); + } + CONTRACTL_END + + ComparePtr *compare = NULL; + if (ptr != NULL) + compare = new ComparePtr(ptr); + + m_HashMap.Init(cbInitialSize, compare, fAsyncMode, pLock); +} + +//--------------------------------------------------------------------- +// HashMap::~HashMap() +// destructor, free the current array of buckets +// +HashMap::~HashMap() +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + // free the current table + Clear(); + // compare object + if (NULL != m_pCompare) + delete m_pCompare; +} + + +//--------------------------------------------------------------------- +// HashMap::Clear() +// Remove all elements from table +// +void HashMap::Clear() +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + // free the current table + delete [] m_rgBuckets; + + m_rgBuckets = NULL; +} + + +//--------------------------------------------------------------------- +// UPTR HashMap::CompareValues(const UPTR value1, const UPTR value2) +// compare values with the function pointer provided +// +#ifndef _DEBUG +inline +#endif +UPTR HashMap::CompareValues(const UPTR value1, const UPTR value2) +{ + WRAPPER_NO_CONTRACT; + +#ifndef _DEBUG + CONTRACTL + { + DISABLED(THROWS); // This is not a bug, we cannot decide, since the function ptr called may be either. + DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either. + } + CONTRACTL_END; +#endif // !_DEBUG + + /// NOTE:: the ordering of arguments are random + return (m_pCompare == NULL || m_pCompare->CompareHelper(value1,value2)); +} + +//--------------------------------------------------------------------- +// bool HashMap::Enter() +// bool HashMap::Leave() +// check valid use of the hash table in synchronus mode + +#ifdef _DEBUG +#ifndef DACCESS_COMPILE +void HashMap::Enter(HashMap *map) +{ + LIMITED_METHOD_CONTRACT; + + // check proper concurrent use of the hash table + if (map->m_fInSyncCode) + ASSERT(0); // oops multiple access to sync.-critical code + map->m_fInSyncCode = true; +} +#else +// In DAC builds, we don't want to take the lock, we just want to know if it's held. If it is, +// we assume the hash map is in an inconsistent state and throw an exception. +// Arguments: +// input: map - the map controlled by the lock. +// Note: Throws +void HashMap::Enter(HashMap *map) +{ + LIMITED_METHOD_DAC_CONTRACT; + + // check proper concurrent use of the hash table + if (map->m_fInSyncCode) + { + ThrowHR(CORDBG_E_PROCESS_NOT_SYNCHRONIZED); // oops multiple access to sync.-critical code + } +} +#endif // DACCESS_COMPILE + +void HashMap::Leave(HashMap *map) +{ + LIMITED_METHOD_CONTRACT; + + // check proper concurrent use of the hash table + if (map->m_fInSyncCode == false) + ASSERT(0); // oops multiple access to sync.-critical code + map->m_fInSyncCode = false; +} +#endif // _DEBUG + +#endif // !DACCESS_COMPILE + +//--------------------------------------------------------------------- +// void HashMap::ProfileLookup(unsigned ntry) +// profile helper code +void HashMap::ProfileLookup(UPTR ntry, UPTR retValue) +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + +#ifndef DACCESS_COMPILE + #ifdef HASHTABLE_PROFILE + if (ntry < HASHTABLE_LOOKUP_PROBES_DATA - 2) + FastInterlockIncrement(&m_rgLookupProbes[ntry]); + else + FastInterlockIncrement(&m_rgLookupProbes[HASHTABLE_LOOKUP_PROBES_DATA - 2]); + + if (retValue == NULL) + { // failure probes + FastInterlockIncrement(&m_rgLookupProbes[HASHTABLE_LOOKUP_PROBES_DATA - 1]); + // the following code is usually executed + // only for special case of lookup done before insert + // check hash.h SyncHash::InsertValue + if (maxFailureProbe < ntry) + { + maxFailureProbe = ntry; + } + } + #endif // HASHTABLE_PROFILE +#endif // !DACCESS_COMPILE +} + +#ifndef DACCESS_COMPILE + +//--------------------------------------------------------------------- +// void HashMap::InsertValue (UPTR key, UPTR value) +// Insert into hash table, if the number of retries +// becomes greater than threshold, expand hash table +// +void HashMap::InsertValue (UPTR key, UPTR value) +{ + STATIC_CONTRACT_THROWS; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FAULT; + + _ASSERTE (OwnLock()); + + // BROKEN: This is called for the RCWCache on the GC thread + GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode); + + ASSERT(m_rgBuckets != NULL); + + // check proper use in synchronous mode + SyncAccessHolder holder(this); // no-op in NON debug code + + ASSERT(value <= VALUE_MASK); + + ASSERT (key > DELETED); + + Bucket* rgBuckets = Buckets(); + DWORD cbSize = GetSize(rgBuckets); + + UINT seed, incr; + HashFunction(key, cbSize, seed, incr); + + for (UPTR ntry =0; ntry < 8; ntry++) + { + Bucket* pBucket = &rgBuckets[seed % cbSize]; + if(pBucket->InsertValue(key,value)) + { + goto LReturn; + } + + seed += incr; + } // for ntry loop + + // We need to expand to keep lookup short + Rehash(); + + // Try again + PutEntry (Buckets(), key,value); + +LReturn: // label for return + + m_cbInserts++; + + #ifdef _DEBUG + ASSERT (m_pCompare != NULL || value == LookupValue (key,value)); + // check proper concurrent use of the hash table in synchronous mode + #endif // _DEBUG + + return; +} +#endif // !DACCESS_COMPILE + +//--------------------------------------------------------------------- +// UPTR HashMap::LookupValue(UPTR key, UPTR value) +// Lookup value in the hash table, use the comparison function +// to verify the values match +// +UPTR HashMap::LookupValue(UPTR key, UPTR value) +{ + CONTRACTL + { + DISABLED(THROWS); // This is not a bug, we cannot decide, since the function ptr called may be either. + DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either. + SO_TOLERANT; + } + CONTRACTL_END; + + SCAN_IGNORE_THROW; // See contract above. + SCAN_IGNORE_TRIGGER; // See contract above. + +#ifndef DACCESS_COMPILE + _ASSERTE (m_fAsyncMode || OwnLock()); + + // BROKEN: This is called for the RCWCache on the GC thread + // Also called by AppDomain::FindCachedAssembly to resolve AssemblyRef -- this is used by stack walking on the GC thread. + // See comments in GCHeap::RestartEE (above the call to SyncClean::CleanUp) for reason to enter COOP mode. + // However, if the current thread is the GC thread, we know we're not going to call GCHeap::RestartEE + // while accessing the HashMap, so it's safe to proceed. + // (m_fAsyncMode && !IsGCThread() is the condition for entering COOP mode. I.e., enable COOP GC only if + // the HashMap is in async mode and this is not a GC thread.) + GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode && !IsGCThread()); + + ASSERT(m_rgBuckets != NULL); + // This is necessary in case some other thread + // replaces m_rgBuckets + ASSERT (key > DELETED); + + // perform this check at lookup time as well + ASSERT(value <= VALUE_MASK); +#endif // !DACCESS_COMPILE + + PTR_Bucket rgBuckets = Buckets(); //atomic fetch + DWORD cbSize = GetSize(rgBuckets); + + UINT seed, incr; + HashFunction(key, cbSize, seed, incr); + + UPTR ntry; + for(ntry =0; ntry < cbSize; ntry++) + { + PTR_Bucket pBucket = rgBuckets+(seed % cbSize); + for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++) + { + if (pBucket->m_rgKeys[i] == key) // keys match + { + + // inline memory barrier call, refer to + // function description at the beginning of this + MemoryBarrier(); + + UPTR storedVal = pBucket->GetValue(i); + // if compare function is provided + // dupe keys are possible, check if the value matches, +// Not using compare function in DAC build. +#ifndef DACCESS_COMPILE + if (CompareValues(value,storedVal)) +#endif + { + ProfileLookup(ntry,storedVal); //no-op in non HASHTABLE_PROFILE code + + // return the stored value + return storedVal; + } + } + } + + seed += incr; + if(!pBucket->IsCollision()) + break; + } // for ntry loop + + // not found + ProfileLookup(ntry,INVALIDENTRY); //no-op in non HASHTABLE_PROFILE code + + return INVALIDENTRY; +} + +#ifndef DACCESS_COMPILE + +//--------------------------------------------------------------------- +// UPTR HashMap::ReplaceValue(UPTR key, UPTR value) +// Replace existing value in the hash table, use the comparison function +// to verify the values match +// +UPTR HashMap::ReplaceValue(UPTR key, UPTR value) +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + _ASSERTE(OwnLock()); + + // BROKEN: This is called for the RCWCache on the GC thread + GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode); + + ASSERT(m_rgBuckets != NULL); + // This is necessary in case some other thread + // replaces m_rgBuckets + ASSERT (key > DELETED); + + // perform this check during replacing as well + ASSERT(value <= VALUE_MASK); + + Bucket* rgBuckets = Buckets(); //atomic fetch + DWORD cbSize = GetSize(rgBuckets); + + UINT seed, incr; + HashFunction(key, cbSize, seed, incr); + + UPTR ntry; + for(ntry =0; ntry < cbSize; ntry++) + { + Bucket* pBucket = &rgBuckets[seed % cbSize]; + for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++) + { + if (pBucket->m_rgKeys[i] == key) // keys match + { + + // inline memory barrier call, refer to + // function description at the beginning of this + MemoryBarrier(); + + UPTR storedVal = pBucket->GetValue(i); + // if compare function is provided + // dupe keys are possible, check if the value matches, + if (CompareValues(value,storedVal)) + { + ProfileLookup(ntry,storedVal); //no-op in non HASHTABLE_PROFILE code + + pBucket->SetValue(value, i); + + // On multiprocessors we should make sure that + // the value is propagated before we proceed. + // inline memory barrier call, refer to + // function description at the beginning of this + MemoryBarrier(); + + // return the previous stored value + return storedVal; + } + } + } + + seed += incr; + if(!pBucket->IsCollision()) + break; + } // for ntry loop + + // not found + ProfileLookup(ntry,INVALIDENTRY); //no-op in non HASHTABLE_PROFILE code + + return INVALIDENTRY; +} + +//--------------------------------------------------------------------- +// UPTR HashMap::DeleteValue (UPTR key, UPTR value) +// if found mark the entry deleted and return the stored value +// +UPTR HashMap::DeleteValue (UPTR key, UPTR value) +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + _ASSERTE (OwnLock()); + + // BROKEN: This is called for the RCWCache on the GC thread + GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode); + + // check proper use in synchronous mode + SyncAccessHolder holoder(this); //no-op in non DEBUG code + + ASSERT(m_rgBuckets != NULL); + // This is necessary in case some other thread + // replaces m_rgBuckets + ASSERT (key > DELETED); + + // perform this check during replacing as well + ASSERT(value <= VALUE_MASK); + + Bucket* rgBuckets = Buckets(); + DWORD cbSize = GetSize(rgBuckets); + + UINT seed, incr; + HashFunction(key, cbSize, seed, incr); + + UPTR ntry; + for(ntry =0; ntry < cbSize; ntry++) + { + Bucket* pBucket = &rgBuckets[seed % cbSize]; + for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++) + { + if (pBucket->m_rgKeys[i] == key) // keys match + { + // inline memory barrier call, refer to + // function description at the beginning of this + MemoryBarrier(); + + UPTR storedVal = pBucket->GetValue(i); + // if compare function is provided + // dupe keys are possible, check if the value matches, + if (CompareValues(value,storedVal)) + { + if(m_fAsyncMode) + { + pBucket->m_rgKeys[i] = DELETED; // mark the key as DELETED + } + else + { + pBucket->m_rgKeys[i] = EMPTY;// otherwise mark the entry as empty + pBucket->SetFreeSlots(); + } + m_cbDeletes++; // track the deletes + + ProfileLookup(ntry,storedVal); //no-op in non HASHTABLE_PROFILE code + + // return the stored value + return storedVal; + } + } + } + + seed += incr; + if(!pBucket->IsCollision()) + break; + } // for ntry loop + + // not found + ProfileLookup(ntry,INVALIDENTRY); //no-op in non HASHTABLE_PROFILE code + +#ifdef _DEBUG + ASSERT (m_pCompare != NULL || (UPTR) INVALIDENTRY == LookupValue (key,value)); + // check proper concurrent use of the hash table in synchronous mode +#endif // _DEBUG + + return INVALIDENTRY; +} + + +//--------------------------------------------------------------------- +// UPTR HashMap::Gethash (UPTR key) +// use this for lookups with unique keys +// don't need to pass an input value to perform the lookup +// +UPTR HashMap::Gethash (UPTR key) +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + return LookupValue(key,NULL); +} + + +//--------------------------------------------------------------------- +// UPTR PutEntry (Bucket* rgBuckets, UPTR key, UPTR value) +// helper used by expand method below + +UPTR HashMap::PutEntry (Bucket* rgBuckets, UPTR key, UPTR value) +{ + CONTRACTL + { + THROWS; + GC_NOTRIGGER; + INJECT_FAULT(COMPlusThrowOM()); + } + CONTRACTL_END + + ASSERT (value > 0); + ASSERT (key > DELETED); + + DWORD size = GetSize(rgBuckets); + UINT seed, incr; + HashFunction(key, size, seed, incr); + + UPTR ntry; + for (ntry =0; ntry < size; ntry++) + { + Bucket* pBucket = &rgBuckets[seed % size]; + if(pBucket->InsertValue(key,value)) + { + return ntry; + } + + seed += incr; + } // for ntry loop + _ASSERTE(!"Hash table insert failed. Bug in PutEntry or the code that resizes the hash table?"); + return INVALIDENTRY; +} + +//--------------------------------------------------------------------- +// +// UPTR HashMap::NewSize() +// compute the new size based on the number of free slots +// +inline +UPTR HashMap::NewSize() +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + ASSERT(m_cbInserts >= m_cbDeletes); + UPTR cbValidSlots = m_cbInserts-m_cbDeletes; + UPTR cbNewSlots = m_cbInserts > m_cbPrevSlotsInUse ? m_cbInserts - m_cbPrevSlotsInUse : 0; + + ASSERT(cbValidSlots >=0 ); + if (cbValidSlots == 0) + return g_rgPrimes[0]; // Minimum size for this hash table. + + UPTR cbTotalSlots = (m_fAsyncMode) ? (UPTR)(cbValidSlots*3/2+cbNewSlots*.6) : cbValidSlots*3/2; + + //UPTR cbTotalSlots = cbSlotsInUse*3/2+m_cbDeletes; + + UPTR iPrimeIndex; + for (iPrimeIndex = 0; iPrimeIndex < g_rgNumPrimes; iPrimeIndex++) + { + if (g_rgPrimes[iPrimeIndex] > cbTotalSlots) + { + return iPrimeIndex; + } + } + ASSERT(iPrimeIndex == g_rgNumPrimes); + ASSERT(0 && !"Hash table walked beyond end of primes array"); + return g_rgNumPrimes - 1; +} + +//--------------------------------------------------------------------- +// void HashMap::Rehash() +// Rehash the hash table, create a new array of buckets and rehash +// all non deleted values from the previous array +// +void HashMap::Rehash() +{ + STATIC_CONTRACT_THROWS; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FAULT; + + // BROKEN: This is called for the RCWCache on the GC thread + GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode); + +#ifndef CROSSGEN_COMPILE + _ASSERTE (!g_fEEStarted || !m_fAsyncMode || GetThread() == NULL || GetThread()->PreemptiveGCDisabled()); + _ASSERTE (OwnLock()); +#endif + + DWORD cbNewSize = g_rgPrimes[m_iPrimeIndex = NewSize()]; + + ASSERT(m_iPrimeIndex < 70); + + Bucket* rgBuckets = Buckets(); + UPTR cbCurrSize = GetSize(rgBuckets); + + S_SIZE_T cbNewBuckets = (S_SIZE_T(cbNewSize) + S_SIZE_T(1)) * S_SIZE_T(sizeof(Bucket)); + + if (cbNewBuckets.IsOverflow()) + ThrowHR(COR_E_OVERFLOW); + + Bucket* rgNewBuckets = (Bucket *) new BYTE[cbNewBuckets.Value()]; + memset (rgNewBuckets, 0, cbNewBuckets.Value()); + SetSize(rgNewBuckets, cbNewSize); + + // current valid slots + UPTR cbValidSlots = m_cbInserts-m_cbDeletes; + m_cbInserts = cbValidSlots; // reset insert count to the new valid count + m_cbPrevSlotsInUse = cbValidSlots; // track the previous delete count + m_cbDeletes = 0; // reset delete count + // rehash table into it + + if (cbValidSlots) // if there are valid slots to be rehashed + { + for (unsigned int nb = 0; nb < cbCurrSize; nb++) + { + for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++) + { + UPTR key =rgBuckets[nb].m_rgKeys[i]; + if (key > DELETED) + { +#ifdef HASHTABLE_PROFILE + UPTR ntry = +#endif + PutEntry (rgNewBuckets+1, key, rgBuckets[nb].GetValue (i)); + #ifdef HASHTABLE_PROFILE + if(ntry >=8) + m_cbInsertProbesGt8++; + #endif // HASHTABLE_PROFILE + + // check if we can bail out + if (--cbValidSlots == 0) + goto LDone; // break out of both the loops + } + } // for i =0 thru SLOTS_PER_BUCKET + } //for all buckets + } + + +LDone: + + Bucket* pObsoleteTables = m_rgBuckets; + + // memory barrier, to replace the pointer to array of bucket + MemoryBarrier(); + + // replace the old array with the new one. + m_rgBuckets = rgNewBuckets; + + #ifdef HASHTABLE_PROFILE + m_cbRehash++; + m_cbRehashSlots+=m_cbInserts; + m_cbObsoleteTables++; // track statistics + m_cbTotalBuckets += (cbNewSize+1); + #endif // HASHTABLE_PROFILE + +#ifdef _DEBUG + + unsigned nb; + if (m_fAsyncMode) + { + // for all non deleted keys in the old table, make sure the corresponding values + // are in the new lookup table + + for (nb = 1; nb <= ((size_t*)pObsoleteTables)[0]; nb++) + { + for (unsigned int i =0; i < SLOTS_PER_BUCKET; i++) + { + if (pObsoleteTables[nb].m_rgKeys[i] > DELETED) + { + UPTR value = pObsoleteTables[nb].GetValue (i); + // make sure the value is present in the new table + ASSERT (m_pCompare != NULL || value == LookupValue (pObsoleteTables[nb].m_rgKeys[i], value)); + } + } + } + } + + // make sure there are no deleted entries in the new lookup table + // if the compare function provided is null, then keys must be unique + for (nb = 0; nb < cbNewSize; nb++) + { + for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++) + { + UPTR keyv = Buckets()[nb].m_rgKeys[i]; + ASSERT (keyv != DELETED); + if (m_pCompare == NULL && keyv != EMPTY) + { + ASSERT ((Buckets()[nb].GetValue (i)) == Gethash (keyv)); + } + } + } +#endif // _DEBUG + + if (m_fAsyncMode) + { + // If we are allowing asynchronous reads, we must delay bucket cleanup until GC time. + SyncClean::AddHashMap (pObsoleteTables); + } + else + { + Bucket* pBucket = pObsoleteTables; + while (pBucket) { + Bucket* pNextBucket = NextObsolete(pBucket); + delete [] pBucket; + pBucket = pNextBucket; + } + } + +} + +//--------------------------------------------------------------------- +// void HashMap::Compact() +// delete obsolete tables, try to compact deleted slots by sliding entries +// in the bucket, note we can slide only if the bucket's collison bit is reset +// otherwise the lookups will break +// @perf, use the m_cbDeletes to m_cbInserts ratio to reduce the size of the hash +// table +// +void HashMap::Compact() +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + + _ASSERTE (OwnLock()); + + // + GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode); + ASSERT(m_rgBuckets != NULL); + + // Try to resize if that makes sense (reduce the size of the table), but + // don't fail the operation simply because we've run out of memory. + UPTR iNewIndex = NewSize(); + if (iNewIndex != m_iPrimeIndex) + { + EX_TRY + { + FAULT_NOT_FATAL(); + Rehash(); + } + EX_CATCH + { + } + EX_END_CATCH(SwallowAllExceptions) + } + + //compact deleted slots, mark them as EMPTY + + if (m_cbDeletes) + { + UPTR cbCurrSize = GetSize(Buckets()); + Bucket *pBucket = Buckets(); + Bucket *pSentinel; + + for (pSentinel = pBucket+cbCurrSize; pBucket < pSentinel; pBucket++) + { //loop thru all buckets + for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++) + { //loop through all slots + if (pBucket->m_rgKeys[i] == DELETED) + { + pBucket->m_rgKeys[i] = EMPTY; + pBucket->SetFreeSlots(); // mark the bucket as containing + // free slots + + // Need to decrement insert and delete counts at the same + // time to preserve correct live count. + _ASSERTE(m_cbInserts >= m_cbDeletes); + --m_cbInserts; + + if(--m_cbDeletes == 0) // decrement count + return; + } + } + } + } + +} + +#ifdef _DEBUG +// A thread must own a lock for a hash if it is a writer. +BOOL HashMap::OwnLock() +{ + STATIC_CONTRACT_NOTHROW; + STATIC_CONTRACT_GC_NOTRIGGER; + STATIC_CONTRACT_FORBID_FAULT; + + DEBUG_ONLY_FUNCTION; + + 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 + +#ifdef HASHTABLE_PROFILE +//--------------------------------------------------------------------- +// void HashMap::DumpStatistics() +// dump statistics collected in profile mode +// +void HashMap::DumpStatistics() +{ + LIMITED_METHOD_CONTRACT; + + cout << "\n Hash Table statistics "<< endl; + cout << "--------------------------------------------------" << endl; + + cout << "Current Insert count " << m_cbInserts << endl; + cout << "Current Delete count "<< m_cbDeletes << endl; + + cout << "Current # of tables " << m_cbObsoleteTables << endl; + cout << "Total # of times Rehashed " << m_cbRehash<< endl; + cout << "Total # of slots rehashed " << m_cbRehashSlots << endl; + + cout << "Insert : Probes gt. 8 during rehash " << m_cbInsertProbesGt8 << endl; + + cout << " Max # of probes for a failed lookup " << maxFailureProbe << endl; + + cout << "Prime Index " << m_iPrimeIndex << endl; + cout << "Current Buckets " << g_rgPrimes[m_iPrimeIndex]+1 << endl; + + cout << "Total Buckets " << m_cbTotalBuckets << endl; + + cout << " Lookup Probes " << endl; + for (unsigned i = 0; i < HASHTABLE_LOOKUP_PROBES_DATA; i++) + { + cout << "# Probes:" << i << " #entries:" << m_rgLookupProbes[i] << endl; + } + cout << "\n--------------------------------------------------" << endl; +} +#endif // HASHTABLE_PROFILE + +#endif // !DACCESS_COMPILE + +#ifdef DACCESS_COMPILE + +void +HashMap::EnumMemoryRegions(CLRDataEnumMemoryFlags flags) +{ + SUPPORTS_DAC; + + // Assumed to be embedded, so no this enumeration. + + if (m_rgBuckets.IsValid()) + { + ULONG32 numBuckets = (ULONG32)GetSize(Buckets()) + 1; + DacEnumMemoryRegion(dac_cast<TADDR>(m_rgBuckets), + numBuckets * sizeof(Bucket)); + + for (size_t i = 0; i < numBuckets; i++) + { + PTR_Bucket bucket = m_rgBuckets + i; + if (bucket.IsValid()) + { + bucket.EnumMem(); + } + } + } +} + +#endif // DACCESS_COMPILE + +#if 0 // Perf test code, enabled on-demand for private testing. +#ifndef DACCESS_COMPILE +// This is for testing purposes only! +void HashMap::HashMapTest() +{ + printf("HashMap test\n"); + + const unsigned int MinValue = 2; // Deleted is reserved, and is 1. + const unsigned int MinThreshold = 10000; + const unsigned int MaxThreshold = 30000; + HashMap * table = new HashMap(); + Crst m_lock("HashMap", CrstSyncHashLock, CrstFlags(CRST_REENTRANCY | CRST_UNSAFE_ANYMODE)); + CrstHolder holder(&m_lock); + LockOwner lock = {&m_lock, IsOwnerOfCrst}; + table->Init(10, (CompareFnPtr) NULL, false, &lock); + for(unsigned int i=MinValue; i < MinThreshold; i++) + table->InsertValue(i, i); + printf("Added %d values.\n", MinThreshold); + //table.DumpStatistics(); + + LookupPerfTest(table, MinThreshold); + + INT64 t0 = GetTickCount(); + INT64 t1; + for(int rep = 0; rep < 10000000; rep++) { + for(unsigned int i=MinThreshold; i < MaxThreshold; i++) { + table->InsertValue(rep + i, rep + i); + } + for(unsigned int i=MinThreshold; i < MaxThreshold; i++) { + table->DeleteValue(rep + i, rep + i); + } + for(unsigned int i=MinValue; i < MinThreshold; i++) + table->DeleteValue(i, i); + for(unsigned int i=MinValue; i < MinThreshold; i++) + table->InsertValue(i, i); + + if (rep % 500 == 0) { + t1 = GetTickCount(); + printf("Repetition %d, took %d ms\n", rep, (int) (t1-t0)); + t0 = t1; + LookupPerfTest(table, MinThreshold); + //table.DumpStatistics(); + } + } + delete table; +} + +// For testing purposes only. +void HashMap::LookupPerfTest(HashMap * table, const unsigned int MinThreshold) +{ + INT64 t0 = GetTickCount(); + for(int rep = 0; rep < 1000; rep++) { + for(unsigned int i=2; i<MinThreshold; i++) { + UPTR v = table->LookupValue(i, i); + if (v != i) { + printf("LookupValue didn't return the expected value!"); + _ASSERTE(v == i); + } + } + } + INT64 t1 = GetTickCount(); + for(unsigned int i = MinThreshold * 80; i < MinThreshold * 80 + 1000; i++) + table->LookupValue(i, i); + //cout << "Lookup perf test (1000 * " << MinThreshold << ": " << (t1-t0) << " ms." << endl; +#ifdef HASHTABLE_PROFILE + printf("Lookup perf test time: %d ms table size: %d max failure probe: %d longest collision chain: %d\n", (int) (t1-t0), (int) table->GetSize(table->Buckets()), (int) table->maxFailureProbe, (int) table->m_cbMaxCollisionLength); + table->DumpStatistics(); +#else // !HASHTABLE_PROFILE + printf("Lookup perf test time: %d ms table size: %d\n", (int) (t1-t0), table->GetSize(table->Buckets())); +#endif // !HASHTABLE_PROFILE +} +#endif // !DACCESS_COMPILE +#endif // 0 // Perf test code, enabled on-demand for private testing. |