1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5
6/*++
7
8Module Name:
9
10 synchash.cpp
11
12--*/
13
14#include "common.h"
15
16#include "hash.h"
17
18#include "excep.h"
19
20#include "syncclean.hpp"
21
22#include "threadsuspend.h"
23
24//---------------------------------------------------------------------
25// Array of primes, used by hash table to choose the number of buckets
26// Review: would we want larger primes? e.g., for 64-bit?
27
28const DWORD g_rgPrimes[] = {
295,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
301103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
3117519,21023,25229,30293,36353,43627,52361,62851,75431,90523, 108631, 130363,
32156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403,
33968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287,
344999559, 5999471, 7199369
35};
36const SIZE_T g_rgNumPrimes = sizeof(g_rgPrimes) / sizeof(*g_rgPrimes);
37
38const unsigned int SLOTS_PER_BUCKET = 4;
39
40#ifndef DACCESS_COMPILE
41
42void *PtrHashMap::operator new(size_t size, LoaderHeap *pHeap)
43{
44 STATIC_CONTRACT_THROWS;
45 STATIC_CONTRACT_GC_NOTRIGGER;
46 STATIC_CONTRACT_FAULT; //return NULL;
47
48 return pHeap->AllocMem(S_SIZE_T(size));
49}
50
51void PtrHashMap::operator delete(void *p)
52{
53}
54
55
56//-----------------------------------------------------------------
57// Bucket methods
58
59BOOL Bucket::InsertValue(const UPTR key, const UPTR value)
60{
61 STATIC_CONTRACT_NOTHROW;
62 STATIC_CONTRACT_GC_NOTRIGGER;
63 STATIC_CONTRACT_FAULT; //return FALSE;
64
65 _ASSERTE(key != EMPTY);
66 _ASSERTE(key != DELETED);
67
68 if (!HasFreeSlots())
69 return false; //no free slots
70
71 // might have a free slot
72 for (UPTR i = 0; i < SLOTS_PER_BUCKET; i++)
73 {
74 //@NOTE we can't reuse DELETED slots
75 if (m_rgKeys[i] == EMPTY)
76 {
77 SetValue (value, i);
78
79 // On multiprocessors we should make sure that
80 // the value is propagated before we proceed.
81 // inline memory barrier call, refer to
82 // function description at the beginning of this
83 MemoryBarrier();
84
85 m_rgKeys[i] = key;
86 return true;
87 }
88 } // for i= 0; i < SLOTS_PER_BUCKET; loop
89
90 SetCollision(); // otherwise set the collision bit
91 return false;
92}
93
94#endif // !DACCESS_COMPILE
95
96//---------------------------------------------------------------------
97// inline Bucket* HashMap::Buckets()
98// get the pointer to the bucket array
99inline
100PTR_Bucket HashMap::Buckets()
101{
102 LIMITED_METHOD_DAC_CONTRACT;
103
104#if !defined(DACCESS_COMPILE) && !defined(CROSSGEN_COMPILE)
105 _ASSERTE (!g_fEEStarted || !m_fAsyncMode || GetThread() == NULL || GetThread()->PreemptiveGCDisabled() || IsGCThread());
106#endif
107 return m_rgBuckets + 1;
108}
109
110//---------------------------------------------------------------------
111// inline size_t HashMap::GetSize(PTR_Bucket rgBuckets)
112// get the number of buckets
113inline
114DWORD HashMap::GetSize(PTR_Bucket rgBuckets)
115{
116 LIMITED_METHOD_DAC_CONTRACT;
117 PTR_size_t pSize = dac_cast<PTR_size_t>(rgBuckets - 1);
118 _ASSERTE(FitsIn<DWORD>(pSize[0]));
119 return static_cast<DWORD>(pSize[0]);
120}
121
122
123//---------------------------------------------------------------------
124// inline size_t HashMap::HashFunction(UPTR key, UINT numBuckets, UINT &seed, UINT &incr)
125// get the first & second hash function.
126// H(key, i) = h1(key) + i*h2(key, hashSize); 0 <= i < numBuckets
127// h2 must return a value >= 1 and < numBuckets.
128inline
129void HashMap::HashFunction(const UPTR key, const UINT numBuckets, UINT &seed, UINT &incr)
130{
131 LIMITED_METHOD_CONTRACT;
132 // First hash function
133 // We commonly use pointers, which are 4 byte aligned, so the two least
134 // significant bits are often 0, then we mod this value by something like
135 // 11. We can get a better distribution for pointers by dividing by 4.
136 // REVIEW: Is 64-bit truncation better or should we be doing something with the
137 // upper 32-bits in either of these hash functions.
138 seed = static_cast<UINT>(key >> 2);
139 // Second hash function
140 incr = (UINT)(1 + (((static_cast<UINT>(key >> 5)) + 1) % ((UINT)numBuckets - 1)));
141 _ASSERTE(incr > 0 && incr < numBuckets);
142}
143
144#ifndef DACCESS_COMPILE
145
146//---------------------------------------------------------------------
147// inline void HashMap::SetSize(Bucket *rgBuckets, size_t size)
148// set the number of buckets
149inline
150void HashMap::SetSize(Bucket *rgBuckets, size_t size)
151{
152 LIMITED_METHOD_CONTRACT;
153 ((size_t*)rgBuckets)[0] = size;
154}
155
156//---------------------------------------------------------------------
157// HashMap::HashMap()
158// constructor, initialize all values
159//
160HashMap::HashMap()
161{
162 STATIC_CONTRACT_NOTHROW;
163 STATIC_CONTRACT_GC_NOTRIGGER;
164 STATIC_CONTRACT_FORBID_FAULT;
165
166 m_rgBuckets = NULL;
167 m_pCompare = NULL; // comparsion object
168 m_cbInserts = 0; // track inserts
169 m_cbDeletes = 0; // track deletes
170 m_cbPrevSlotsInUse = 0; // track valid slots present during previous rehash
171
172 //Debug data member
173#ifdef _DEBUG
174 m_fInSyncCode = false;
175#endif
176 // profile data members
177#ifdef HASHTABLE_PROFILE
178 m_cbRehash = 0;
179 m_cbRehashSlots = 0;
180 m_cbObsoleteTables = 0;
181 m_cbTotalBuckets =0;
182 m_cbInsertProbesGt8 = 0; // inserts that needed more than 8 probes
183 maxFailureProbe =0;
184 memset(m_rgLookupProbes,0,HASHTABLE_LOOKUP_PROBES_DATA*sizeof(LONG));
185#endif // HASHTABLE_PROFILE
186#ifdef _DEBUG
187 m_lockData = NULL;
188 m_pfnLockOwner = NULL;
189#endif // _DEBUG
190}
191
192//---------------------------------------------------------------------
193// void HashMap::Init(unsigned cbInitialSize, CompareFnPtr ptr, bool fAsyncMode)
194// set the initial size of the hash table and provide the comparison
195// function pointer
196//
197void HashMap::Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock)
198{
199 CONTRACTL
200 {
201 THROWS;
202 GC_NOTRIGGER;
203 INJECT_FAULT(COMPlusThrowOM());
204 }
205 CONTRACTL_END
206
207 Compare* pCompare = NULL;
208 if (ptr != NULL)
209 {
210 pCompare = new Compare(ptr);
211 }
212 Init(cbInitialSize, pCompare, fAsyncMode, pLock);
213}
214
215DWORD HashMap::GetNearestIndex(DWORD cbInitialSize)
216{
217 LIMITED_METHOD_CONTRACT;
218
219 DWORD lowIndex = 0;
220 DWORD highIndex = g_rgNumPrimes - 1;
221 DWORD midIndex = (highIndex + 1) / 2;
222
223 if (cbInitialSize <= g_rgPrimes[0])
224 return 0;
225
226 if (cbInitialSize >= g_rgPrimes[highIndex])
227 return highIndex;
228
229 while (true)
230 {
231 if (cbInitialSize < g_rgPrimes[midIndex])
232 {
233 highIndex = midIndex;
234 }
235 else
236 {
237 if (cbInitialSize == g_rgPrimes[midIndex])
238 return midIndex;
239 lowIndex = midIndex;
240 }
241 midIndex = lowIndex + (highIndex - lowIndex + 1)/2;
242 if (highIndex == midIndex)
243 {
244 _ASSERTE(g_rgPrimes[highIndex] >= cbInitialSize);
245 _ASSERTE(highIndex < g_rgNumPrimes);
246 return highIndex;
247 }
248 }
249}
250
251//---------------------------------------------------------------------
252// void HashMap::Init(unsigned cbInitialSize, Compare* pCompare, bool fAsyncMode)
253// set the initial size of the hash table and provide the comparison
254// function pointer
255//
256void HashMap::Init(DWORD cbInitialSize, Compare* pCompare, BOOL fAsyncMode, LockOwner *pLock)
257{
258 CONTRACTL
259 {
260 THROWS;
261 GC_NOTRIGGER;
262 INJECT_FAULT(COMPlusThrowOM());
263 }
264 CONTRACTL_END
265
266 m_iPrimeIndex = GetNearestIndex(cbInitialSize);
267 DWORD size = g_rgPrimes[m_iPrimeIndex];
268 PREFIX_ASSUME(size < 0x7fffffff);
269
270 m_rgBuckets = new Bucket[size+1];
271
272 memset (m_rgBuckets, 0, (size+1)*sizeof(Bucket));
273 SetSize(m_rgBuckets, size);
274
275 m_pCompare = pCompare;
276
277 m_fAsyncMode = fAsyncMode != FALSE;
278
279 // assert null comparison returns true
280 //ASSERT(
281 // m_pCompare == NULL ||
282 // (m_pCompare->CompareHelper(0,0) != 0)
283 // );
284
285#ifdef HASHTABLE_PROFILE
286 m_cbTotalBuckets = size+1;
287#endif
288
289#ifdef _DEBUG
290 if (pLock == NULL) {
291 m_lockData = NULL;
292 m_pfnLockOwner = NULL;
293 }
294 else
295 {
296 m_lockData = pLock->lock;
297 m_pfnLockOwner = pLock->lockOwnerFunc;
298 }
299 if (m_pfnLockOwner == NULL) {
300 m_writerThreadId.SetToCurrentThread();
301 }
302#endif // _DEBUG
303}
304
305//---------------------------------------------------------------------
306// void PtrHashMap::Init(unsigned cbInitialSize, CompareFnPtr ptr, bool fAsyncMode)
307// set the initial size of the hash table and provide the comparison
308// function pointer
309//
310void PtrHashMap::Init(DWORD cbInitialSize, CompareFnPtr ptr, BOOL fAsyncMode, LockOwner *pLock)
311{
312 CONTRACTL
313 {
314 THROWS;
315 GC_NOTRIGGER;
316 INJECT_FAULT(COMPlusThrowOM());
317 }
318 CONTRACTL_END
319
320 ComparePtr *compare = NULL;
321 if (ptr != NULL)
322 compare = new ComparePtr(ptr);
323
324 m_HashMap.Init(cbInitialSize, compare, fAsyncMode, pLock);
325}
326
327//---------------------------------------------------------------------
328// HashMap::~HashMap()
329// destructor, free the current array of buckets
330//
331HashMap::~HashMap()
332{
333 STATIC_CONTRACT_NOTHROW;
334 STATIC_CONTRACT_GC_NOTRIGGER;
335 STATIC_CONTRACT_FORBID_FAULT;
336
337 // free the current table
338 Clear();
339 // compare object
340 if (NULL != m_pCompare)
341 delete m_pCompare;
342}
343
344
345//---------------------------------------------------------------------
346// HashMap::Clear()
347// Remove all elements from table
348//
349void HashMap::Clear()
350{
351 STATIC_CONTRACT_NOTHROW;
352 STATIC_CONTRACT_GC_NOTRIGGER;
353 STATIC_CONTRACT_FORBID_FAULT;
354
355 // free the current table
356 delete [] m_rgBuckets;
357
358 m_rgBuckets = NULL;
359}
360
361
362//---------------------------------------------------------------------
363// UPTR HashMap::CompareValues(const UPTR value1, const UPTR value2)
364// compare values with the function pointer provided
365//
366#ifndef _DEBUG
367inline
368#endif
369UPTR HashMap::CompareValues(const UPTR value1, const UPTR value2)
370{
371 WRAPPER_NO_CONTRACT;
372
373#ifndef _DEBUG
374 CONTRACTL
375 {
376 DISABLED(THROWS); // This is not a bug, we cannot decide, since the function ptr called may be either.
377 DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either.
378 }
379 CONTRACTL_END;
380#endif // !_DEBUG
381
382 /// NOTE:: the ordering of arguments are random
383 return (m_pCompare == NULL || m_pCompare->CompareHelper(value1,value2));
384}
385
386//---------------------------------------------------------------------
387// bool HashMap::Enter()
388// bool HashMap::Leave()
389// check valid use of the hash table in synchronus mode
390
391#ifdef _DEBUG
392#ifndef DACCESS_COMPILE
393void HashMap::Enter(HashMap *map)
394{
395 LIMITED_METHOD_CONTRACT;
396
397 // check proper concurrent use of the hash table
398 if (map->m_fInSyncCode)
399 ASSERT(0); // oops multiple access to sync.-critical code
400 map->m_fInSyncCode = true;
401}
402#else
403// In DAC builds, we don't want to take the lock, we just want to know if it's held. If it is,
404// we assume the hash map is in an inconsistent state and throw an exception.
405// Arguments:
406// input: map - the map controlled by the lock.
407// Note: Throws
408void HashMap::Enter(HashMap *map)
409{
410 LIMITED_METHOD_DAC_CONTRACT;
411
412 // check proper concurrent use of the hash table
413 if (map->m_fInSyncCode)
414 {
415 ThrowHR(CORDBG_E_PROCESS_NOT_SYNCHRONIZED); // oops multiple access to sync.-critical code
416 }
417}
418#endif // DACCESS_COMPILE
419
420void HashMap::Leave(HashMap *map)
421{
422 LIMITED_METHOD_CONTRACT;
423
424 // check proper concurrent use of the hash table
425 if (map->m_fInSyncCode == false)
426 ASSERT(0); // oops multiple access to sync.-critical code
427 map->m_fInSyncCode = false;
428}
429#endif // _DEBUG
430
431#endif // !DACCESS_COMPILE
432
433//---------------------------------------------------------------------
434// void HashMap::ProfileLookup(unsigned ntry)
435// profile helper code
436void HashMap::ProfileLookup(UPTR ntry, UPTR retValue)
437{
438 STATIC_CONTRACT_NOTHROW;
439 STATIC_CONTRACT_GC_NOTRIGGER;
440 STATIC_CONTRACT_FORBID_FAULT;
441
442#ifndef DACCESS_COMPILE
443 #ifdef HASHTABLE_PROFILE
444 if (ntry < HASHTABLE_LOOKUP_PROBES_DATA - 2)
445 FastInterlockIncrement(&m_rgLookupProbes[ntry]);
446 else
447 FastInterlockIncrement(&m_rgLookupProbes[HASHTABLE_LOOKUP_PROBES_DATA - 2]);
448
449 if (retValue == NULL)
450 { // failure probes
451 FastInterlockIncrement(&m_rgLookupProbes[HASHTABLE_LOOKUP_PROBES_DATA - 1]);
452 // the following code is usually executed
453 // only for special case of lookup done before insert
454 // check hash.h SyncHash::InsertValue
455 if (maxFailureProbe < ntry)
456 {
457 maxFailureProbe = ntry;
458 }
459 }
460 #endif // HASHTABLE_PROFILE
461#endif // !DACCESS_COMPILE
462}
463
464#ifndef DACCESS_COMPILE
465
466//---------------------------------------------------------------------
467// void HashMap::InsertValue (UPTR key, UPTR value)
468// Insert into hash table, if the number of retries
469// becomes greater than threshold, expand hash table
470//
471void HashMap::InsertValue (UPTR key, UPTR value)
472{
473 STATIC_CONTRACT_THROWS;
474 STATIC_CONTRACT_GC_NOTRIGGER;
475 STATIC_CONTRACT_FAULT;
476
477 _ASSERTE (OwnLock());
478
479 // BROKEN: This is called for the RCWCache on the GC thread
480 GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode);
481
482 ASSERT(m_rgBuckets != NULL);
483
484 // check proper use in synchronous mode
485 SyncAccessHolder holder(this); // no-op in NON debug code
486
487 ASSERT(value <= VALUE_MASK);
488
489 ASSERT (key > DELETED);
490
491 Bucket* rgBuckets = Buckets();
492 DWORD cbSize = GetSize(rgBuckets);
493
494 UINT seed, incr;
495 HashFunction(key, cbSize, seed, incr);
496
497 for (UPTR ntry =0; ntry < 8; ntry++)
498 {
499 Bucket* pBucket = &rgBuckets[seed % cbSize];
500 if(pBucket->InsertValue(key,value))
501 {
502 goto LReturn;
503 }
504
505 seed += incr;
506 } // for ntry loop
507
508 // We need to expand to keep lookup short
509 Rehash();
510
511 // Try again
512 PutEntry (Buckets(), key,value);
513
514LReturn: // label for return
515
516 m_cbInserts++;
517
518 #ifdef _DEBUG
519 ASSERT (m_pCompare != NULL || value == LookupValue (key,value));
520 // check proper concurrent use of the hash table in synchronous mode
521 #endif // _DEBUG
522
523 return;
524}
525#endif // !DACCESS_COMPILE
526
527//---------------------------------------------------------------------
528// UPTR HashMap::LookupValue(UPTR key, UPTR value)
529// Lookup value in the hash table, use the comparison function
530// to verify the values match
531//
532UPTR HashMap::LookupValue(UPTR key, UPTR value)
533{
534 CONTRACTL
535 {
536 DISABLED(THROWS); // This is not a bug, we cannot decide, since the function ptr called may be either.
537 DISABLED(GC_NOTRIGGER); // This is not a bug, we cannot decide, since the function ptr called may be either.
538 SO_TOLERANT;
539 }
540 CONTRACTL_END;
541
542 SCAN_IGNORE_THROW; // See contract above.
543 SCAN_IGNORE_TRIGGER; // See contract above.
544
545#ifndef DACCESS_COMPILE
546 _ASSERTE (m_fAsyncMode || OwnLock());
547
548 // BROKEN: This is called for the RCWCache on the GC thread
549 // Also called by AppDomain::FindCachedAssembly to resolve AssemblyRef -- this is used by stack walking on the GC thread.
550 // See comments in GCHeapUtilities::RestartEE (above the call to SyncClean::CleanUp) for reason to enter COOP mode.
551 // However, if the current thread is the GC thread, we know we're not going to call GCHeapUtilities::RestartEE
552 // while accessing the HashMap, so it's safe to proceed.
553 // (m_fAsyncMode && !IsGCThread() is the condition for entering COOP mode. I.e., enable COOP GC only if
554 // the HashMap is in async mode and this is not a GC thread.)
555 GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode && !IsGCThread());
556
557 ASSERT(m_rgBuckets != NULL);
558 // This is necessary in case some other thread
559 // replaces m_rgBuckets
560 ASSERT (key > DELETED);
561
562 // perform this check at lookup time as well
563 ASSERT(value <= VALUE_MASK);
564#endif // !DACCESS_COMPILE
565
566 PTR_Bucket rgBuckets = Buckets(); //atomic fetch
567 DWORD cbSize = GetSize(rgBuckets);
568
569 UINT seed, incr;
570 HashFunction(key, cbSize, seed, incr);
571
572 UPTR ntry;
573 for(ntry =0; ntry < cbSize; ntry++)
574 {
575 PTR_Bucket pBucket = rgBuckets+(seed % cbSize);
576 for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++)
577 {
578 if (pBucket->m_rgKeys[i] == key) // keys match
579 {
580
581 // inline memory barrier call, refer to
582 // function description at the beginning of this
583 MemoryBarrier();
584
585 UPTR storedVal = pBucket->GetValue(i);
586 // if compare function is provided
587 // dupe keys are possible, check if the value matches,
588// Not using compare function in DAC build.
589#ifndef DACCESS_COMPILE
590 if (CompareValues(value,storedVal))
591#endif
592 {
593 ProfileLookup(ntry,storedVal); //no-op in non HASHTABLE_PROFILE code
594
595 // return the stored value
596 return storedVal;
597 }
598 }
599 }
600
601 seed += incr;
602 if(!pBucket->IsCollision())
603 break;
604 } // for ntry loop
605
606 // not found
607 ProfileLookup(ntry,INVALIDENTRY); //no-op in non HASHTABLE_PROFILE code
608
609 return INVALIDENTRY;
610}
611
612#ifndef DACCESS_COMPILE
613
614//---------------------------------------------------------------------
615// UPTR HashMap::ReplaceValue(UPTR key, UPTR value)
616// Replace existing value in the hash table, use the comparison function
617// to verify the values match
618//
619UPTR HashMap::ReplaceValue(UPTR key, UPTR value)
620{
621 STATIC_CONTRACT_NOTHROW;
622 STATIC_CONTRACT_GC_NOTRIGGER;
623 STATIC_CONTRACT_FORBID_FAULT;
624
625 _ASSERTE(OwnLock());
626
627 // BROKEN: This is called for the RCWCache on the GC thread
628 GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode);
629
630 ASSERT(m_rgBuckets != NULL);
631 // This is necessary in case some other thread
632 // replaces m_rgBuckets
633 ASSERT (key > DELETED);
634
635 // perform this check during replacing as well
636 ASSERT(value <= VALUE_MASK);
637
638 Bucket* rgBuckets = Buckets(); //atomic fetch
639 DWORD cbSize = GetSize(rgBuckets);
640
641 UINT seed, incr;
642 HashFunction(key, cbSize, seed, incr);
643
644 UPTR ntry;
645 for(ntry =0; ntry < cbSize; ntry++)
646 {
647 Bucket* pBucket = &rgBuckets[seed % cbSize];
648 for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++)
649 {
650 if (pBucket->m_rgKeys[i] == key) // keys match
651 {
652
653 // inline memory barrier call, refer to
654 // function description at the beginning of this
655 MemoryBarrier();
656
657 UPTR storedVal = pBucket->GetValue(i);
658 // if compare function is provided
659 // dupe keys are possible, check if the value matches,
660 if (CompareValues(value,storedVal))
661 {
662 ProfileLookup(ntry,storedVal); //no-op in non HASHTABLE_PROFILE code
663
664 pBucket->SetValue(value, i);
665
666 // On multiprocessors we should make sure that
667 // the value is propagated before we proceed.
668 // inline memory barrier call, refer to
669 // function description at the beginning of this
670 MemoryBarrier();
671
672 // return the previous stored value
673 return storedVal;
674 }
675 }
676 }
677
678 seed += incr;
679 if(!pBucket->IsCollision())
680 break;
681 } // for ntry loop
682
683 // not found
684 ProfileLookup(ntry,INVALIDENTRY); //no-op in non HASHTABLE_PROFILE code
685
686 return INVALIDENTRY;
687}
688
689//---------------------------------------------------------------------
690// UPTR HashMap::DeleteValue (UPTR key, UPTR value)
691// if found mark the entry deleted and return the stored value
692//
693UPTR HashMap::DeleteValue (UPTR key, UPTR value)
694{
695 STATIC_CONTRACT_NOTHROW;
696 STATIC_CONTRACT_GC_NOTRIGGER;
697 STATIC_CONTRACT_FORBID_FAULT;
698
699 _ASSERTE (OwnLock());
700
701 // BROKEN: This is called for the RCWCache on the GC thread
702 GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode);
703
704 // check proper use in synchronous mode
705 SyncAccessHolder holoder(this); //no-op in non DEBUG code
706
707 ASSERT(m_rgBuckets != NULL);
708 // This is necessary in case some other thread
709 // replaces m_rgBuckets
710 ASSERT (key > DELETED);
711
712 // perform this check during replacing as well
713 ASSERT(value <= VALUE_MASK);
714
715 Bucket* rgBuckets = Buckets();
716 DWORD cbSize = GetSize(rgBuckets);
717
718 UINT seed, incr;
719 HashFunction(key, cbSize, seed, incr);
720
721 UPTR ntry;
722 for(ntry =0; ntry < cbSize; ntry++)
723 {
724 Bucket* pBucket = &rgBuckets[seed % cbSize];
725 for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++)
726 {
727 if (pBucket->m_rgKeys[i] == key) // keys match
728 {
729 // inline memory barrier call, refer to
730 // function description at the beginning of this
731 MemoryBarrier();
732
733 UPTR storedVal = pBucket->GetValue(i);
734 // if compare function is provided
735 // dupe keys are possible, check if the value matches,
736 if (CompareValues(value,storedVal))
737 {
738 if(m_fAsyncMode)
739 {
740 pBucket->m_rgKeys[i] = DELETED; // mark the key as DELETED
741 }
742 else
743 {
744 pBucket->m_rgKeys[i] = EMPTY;// otherwise mark the entry as empty
745 pBucket->SetFreeSlots();
746 }
747 m_cbDeletes++; // track the deletes
748
749 ProfileLookup(ntry,storedVal); //no-op in non HASHTABLE_PROFILE code
750
751 // return the stored value
752 return storedVal;
753 }
754 }
755 }
756
757 seed += incr;
758 if(!pBucket->IsCollision())
759 break;
760 } // for ntry loop
761
762 // not found
763 ProfileLookup(ntry,INVALIDENTRY); //no-op in non HASHTABLE_PROFILE code
764
765#ifdef _DEBUG
766 ASSERT (m_pCompare != NULL || (UPTR) INVALIDENTRY == LookupValue (key,value));
767 // check proper concurrent use of the hash table in synchronous mode
768#endif // _DEBUG
769
770 return INVALIDENTRY;
771}
772
773
774//---------------------------------------------------------------------
775// UPTR HashMap::Gethash (UPTR key)
776// use this for lookups with unique keys
777// don't need to pass an input value to perform the lookup
778//
779UPTR HashMap::Gethash (UPTR key)
780{
781 STATIC_CONTRACT_NOTHROW;
782 STATIC_CONTRACT_GC_NOTRIGGER;
783 STATIC_CONTRACT_FORBID_FAULT;
784
785 return LookupValue(key,NULL);
786}
787
788
789//---------------------------------------------------------------------
790// UPTR PutEntry (Bucket* rgBuckets, UPTR key, UPTR value)
791// helper used by expand method below
792
793UPTR HashMap::PutEntry (Bucket* rgBuckets, UPTR key, UPTR value)
794{
795 CONTRACTL
796 {
797 THROWS;
798 GC_NOTRIGGER;
799 INJECT_FAULT(COMPlusThrowOM());
800 }
801 CONTRACTL_END
802
803 ASSERT (value > 0);
804 ASSERT (key > DELETED);
805
806 DWORD size = GetSize(rgBuckets);
807 UINT seed, incr;
808 HashFunction(key, size, seed, incr);
809
810 UPTR ntry;
811 for (ntry =0; ntry < size; ntry++)
812 {
813 Bucket* pBucket = &rgBuckets[seed % size];
814 if(pBucket->InsertValue(key,value))
815 {
816 return ntry;
817 }
818
819 seed += incr;
820 } // for ntry loop
821 _ASSERTE(!"Hash table insert failed. Bug in PutEntry or the code that resizes the hash table?");
822 return INVALIDENTRY;
823}
824
825//---------------------------------------------------------------------
826//
827// UPTR HashMap::NewSize()
828// compute the new size based on the number of free slots
829//
830inline
831UPTR HashMap::NewSize()
832{
833 STATIC_CONTRACT_NOTHROW;
834 STATIC_CONTRACT_GC_NOTRIGGER;
835 STATIC_CONTRACT_FORBID_FAULT;
836
837 ASSERT(m_cbInserts >= m_cbDeletes);
838 UPTR cbValidSlots = m_cbInserts-m_cbDeletes;
839 UPTR cbNewSlots = m_cbInserts > m_cbPrevSlotsInUse ? m_cbInserts - m_cbPrevSlotsInUse : 0;
840
841 ASSERT(cbValidSlots >=0 );
842 if (cbValidSlots == 0)
843 return g_rgPrimes[0]; // Minimum size for this hash table.
844
845 UPTR cbTotalSlots = (m_fAsyncMode) ? (UPTR)(cbValidSlots*3/2+cbNewSlots*.6) : cbValidSlots*3/2;
846
847 //UPTR cbTotalSlots = cbSlotsInUse*3/2+m_cbDeletes;
848
849 UPTR iPrimeIndex;
850 for (iPrimeIndex = 0; iPrimeIndex < g_rgNumPrimes; iPrimeIndex++)
851 {
852 if (g_rgPrimes[iPrimeIndex] > cbTotalSlots)
853 {
854 return iPrimeIndex;
855 }
856 }
857 ASSERT(iPrimeIndex == g_rgNumPrimes);
858 ASSERT(0 && !"Hash table walked beyond end of primes array");
859 return g_rgNumPrimes - 1;
860}
861
862//---------------------------------------------------------------------
863// void HashMap::Rehash()
864// Rehash the hash table, create a new array of buckets and rehash
865// all non deleted values from the previous array
866//
867void HashMap::Rehash()
868{
869 STATIC_CONTRACT_THROWS;
870 STATIC_CONTRACT_GC_NOTRIGGER;
871 STATIC_CONTRACT_FAULT;
872
873 // BROKEN: This is called for the RCWCache on the GC thread
874 GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode);
875
876#ifndef CROSSGEN_COMPILE
877 _ASSERTE (!g_fEEStarted || !m_fAsyncMode || GetThread() == NULL || GetThread()->PreemptiveGCDisabled());
878 _ASSERTE (OwnLock());
879#endif
880
881 UPTR newPrimeIndex = NewSize();
882
883 ASSERT(newPrimeIndex < g_rgNumPrimes);
884
885 if ((m_iPrimeIndex == newPrimeIndex) && (m_cbDeletes == 0))
886 {
887 return;
888 }
889
890 m_iPrimeIndex = newPrimeIndex;
891
892 DWORD cbNewSize = g_rgPrimes[m_iPrimeIndex];
893
894 Bucket* rgBuckets = Buckets();
895 UPTR cbCurrSize = GetSize(rgBuckets);
896
897 S_SIZE_T cbNewBuckets = (S_SIZE_T(cbNewSize) + S_SIZE_T(1)) * S_SIZE_T(sizeof(Bucket));
898
899 if (cbNewBuckets.IsOverflow())
900 ThrowHR(COR_E_OVERFLOW);
901
902 Bucket* rgNewBuckets = (Bucket *) new BYTE[cbNewBuckets.Value()];
903 memset (rgNewBuckets, 0, cbNewBuckets.Value());
904 SetSize(rgNewBuckets, cbNewSize);
905
906 // current valid slots
907 UPTR cbValidSlots = m_cbInserts-m_cbDeletes;
908 m_cbInserts = cbValidSlots; // reset insert count to the new valid count
909 m_cbPrevSlotsInUse = cbValidSlots; // track the previous delete count
910 m_cbDeletes = 0; // reset delete count
911 // rehash table into it
912
913 if (cbValidSlots) // if there are valid slots to be rehashed
914 {
915 for (unsigned int nb = 0; nb < cbCurrSize; nb++)
916 {
917 for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++)
918 {
919 UPTR key =rgBuckets[nb].m_rgKeys[i];
920 if (key > DELETED)
921 {
922#ifdef HASHTABLE_PROFILE
923 UPTR ntry =
924#endif
925 PutEntry (rgNewBuckets+1, key, rgBuckets[nb].GetValue (i));
926 #ifdef HASHTABLE_PROFILE
927 if(ntry >=8)
928 m_cbInsertProbesGt8++;
929 #endif // HASHTABLE_PROFILE
930
931 // check if we can bail out
932 if (--cbValidSlots == 0)
933 goto LDone; // break out of both the loops
934 }
935 } // for i =0 thru SLOTS_PER_BUCKET
936 } //for all buckets
937 }
938
939
940LDone:
941
942 Bucket* pObsoleteTables = m_rgBuckets;
943
944 // memory barrier, to replace the pointer to array of bucket
945 MemoryBarrier();
946
947 // replace the old array with the new one.
948 m_rgBuckets = rgNewBuckets;
949
950 #ifdef HASHTABLE_PROFILE
951 m_cbRehash++;
952 m_cbRehashSlots+=m_cbInserts;
953 m_cbObsoleteTables++; // track statistics
954 m_cbTotalBuckets += (cbNewSize+1);
955 #endif // HASHTABLE_PROFILE
956
957#ifdef _DEBUG
958
959 unsigned nb;
960 if (m_fAsyncMode)
961 {
962 // for all non deleted keys in the old table, make sure the corresponding values
963 // are in the new lookup table
964
965 for (nb = 1; nb <= ((size_t*)pObsoleteTables)[0]; nb++)
966 {
967 for (unsigned int i =0; i < SLOTS_PER_BUCKET; i++)
968 {
969 if (pObsoleteTables[nb].m_rgKeys[i] > DELETED)
970 {
971 UPTR value = pObsoleteTables[nb].GetValue (i);
972 // make sure the value is present in the new table
973 ASSERT (m_pCompare != NULL || value == LookupValue (pObsoleteTables[nb].m_rgKeys[i], value));
974 }
975 }
976 }
977 }
978
979 // make sure there are no deleted entries in the new lookup table
980 // if the compare function provided is null, then keys must be unique
981 for (nb = 0; nb < cbNewSize; nb++)
982 {
983 for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++)
984 {
985 UPTR keyv = Buckets()[nb].m_rgKeys[i];
986 ASSERT (keyv != DELETED);
987 if (m_pCompare == NULL && keyv != EMPTY)
988 {
989 ASSERT ((Buckets()[nb].GetValue (i)) == Gethash (keyv));
990 }
991 }
992 }
993#endif // _DEBUG
994
995 if (m_fAsyncMode)
996 {
997 // If we are allowing asynchronous reads, we must delay bucket cleanup until GC time.
998 SyncClean::AddHashMap (pObsoleteTables);
999 }
1000 else
1001 {
1002 Bucket* pBucket = pObsoleteTables;
1003 while (pBucket) {
1004 Bucket* pNextBucket = NextObsolete(pBucket);
1005 delete [] pBucket;
1006 pBucket = pNextBucket;
1007 }
1008 }
1009
1010}
1011
1012//---------------------------------------------------------------------
1013// void HashMap::Compact()
1014// delete obsolete tables, try to compact deleted slots by sliding entries
1015// in the bucket, note we can slide only if the bucket's collison bit is reset
1016// otherwise the lookups will break
1017// @perf, use the m_cbDeletes to m_cbInserts ratio to reduce the size of the hash
1018// table
1019//
1020void HashMap::Compact()
1021{
1022 STATIC_CONTRACT_NOTHROW;
1023 STATIC_CONTRACT_GC_NOTRIGGER;
1024
1025 _ASSERTE (OwnLock());
1026
1027 //
1028 GCX_MAYBE_COOP_NO_THREAD_BROKEN(m_fAsyncMode);
1029 ASSERT(m_rgBuckets != NULL);
1030
1031 // Try to resize if that makes sense (reduce the size of the table), but
1032 // don't fail the operation simply because we've run out of memory.
1033 UPTR iNewIndex = NewSize();
1034 if (iNewIndex != m_iPrimeIndex)
1035 {
1036 EX_TRY
1037 {
1038 FAULT_NOT_FATAL();
1039 Rehash();
1040 }
1041 EX_CATCH
1042 {
1043 }
1044 EX_END_CATCH(SwallowAllExceptions)
1045 }
1046
1047 //compact deleted slots, mark them as EMPTY
1048
1049 if (m_cbDeletes)
1050 {
1051 UPTR cbCurrSize = GetSize(Buckets());
1052 Bucket *pBucket = Buckets();
1053 Bucket *pSentinel;
1054
1055 for (pSentinel = pBucket+cbCurrSize; pBucket < pSentinel; pBucket++)
1056 { //loop thru all buckets
1057 for (unsigned int i = 0; i < SLOTS_PER_BUCKET; i++)
1058 { //loop through all slots
1059 if (pBucket->m_rgKeys[i] == DELETED)
1060 {
1061 pBucket->m_rgKeys[i] = EMPTY;
1062 pBucket->SetFreeSlots(); // mark the bucket as containing
1063 // free slots
1064
1065 // Need to decrement insert and delete counts at the same
1066 // time to preserve correct live count.
1067 _ASSERTE(m_cbInserts >= m_cbDeletes);
1068 --m_cbInserts;
1069
1070 if(--m_cbDeletes == 0) // decrement count
1071 return;
1072 }
1073 }
1074 }
1075 }
1076
1077}
1078
1079#ifdef _DEBUG
1080// A thread must own a lock for a hash if it is a writer.
1081BOOL HashMap::OwnLock()
1082{
1083 STATIC_CONTRACT_NOTHROW;
1084 STATIC_CONTRACT_GC_NOTRIGGER;
1085 STATIC_CONTRACT_FORBID_FAULT;
1086
1087 DEBUG_ONLY_FUNCTION;
1088
1089 if (m_pfnLockOwner == NULL) {
1090 return m_writerThreadId.IsCurrentThread();
1091 }
1092 else {
1093 BOOL ret = m_pfnLockOwner(m_lockData);
1094 if (!ret) {
1095 if (Debug_IsLockedViaThreadSuspension()) {
1096 ret = TRUE;
1097 }
1098 }
1099 return ret;
1100 }
1101}
1102#endif // _DEBUG
1103
1104#ifdef HASHTABLE_PROFILE
1105//---------------------------------------------------------------------
1106// void HashMap::DumpStatistics()
1107// dump statistics collected in profile mode
1108//
1109void HashMap::DumpStatistics()
1110{
1111 LIMITED_METHOD_CONTRACT;
1112
1113 cout << "\n Hash Table statistics "<< endl;
1114 cout << "--------------------------------------------------" << endl;
1115
1116 cout << "Current Insert count " << m_cbInserts << endl;
1117 cout << "Current Delete count "<< m_cbDeletes << endl;
1118
1119 cout << "Current # of tables " << m_cbObsoleteTables << endl;
1120 cout << "Total # of times Rehashed " << m_cbRehash<< endl;
1121 cout << "Total # of slots rehashed " << m_cbRehashSlots << endl;
1122
1123 cout << "Insert : Probes gt. 8 during rehash " << m_cbInsertProbesGt8 << endl;
1124
1125 cout << " Max # of probes for a failed lookup " << maxFailureProbe << endl;
1126
1127 cout << "Prime Index " << m_iPrimeIndex << endl;
1128 cout << "Current Buckets " << g_rgPrimes[m_iPrimeIndex]+1 << endl;
1129
1130 cout << "Total Buckets " << m_cbTotalBuckets << endl;
1131
1132 cout << " Lookup Probes " << endl;
1133 for (unsigned i = 0; i < HASHTABLE_LOOKUP_PROBES_DATA; i++)
1134 {
1135 cout << "# Probes:" << i << " #entries:" << m_rgLookupProbes[i] << endl;
1136 }
1137 cout << "\n--------------------------------------------------" << endl;
1138}
1139#endif // HASHTABLE_PROFILE
1140
1141#endif // !DACCESS_COMPILE
1142
1143#ifdef DACCESS_COMPILE
1144
1145void
1146HashMap::EnumMemoryRegions(CLRDataEnumMemoryFlags flags)
1147{
1148 SUPPORTS_DAC;
1149
1150 // Assumed to be embedded, so no this enumeration.
1151
1152 if (m_rgBuckets.IsValid())
1153 {
1154 ULONG32 numBuckets = (ULONG32)GetSize(Buckets()) + 1;
1155 DacEnumMemoryRegion(dac_cast<TADDR>(m_rgBuckets),
1156 numBuckets * sizeof(Bucket));
1157
1158 for (size_t i = 0; i < numBuckets; i++)
1159 {
1160 PTR_Bucket bucket = m_rgBuckets + i;
1161 if (bucket.IsValid())
1162 {
1163 bucket.EnumMem();
1164 }
1165 }
1166 }
1167}
1168
1169#endif // DACCESS_COMPILE
1170
1171#if 0 // Perf test code, enabled on-demand for private testing.
1172#ifndef DACCESS_COMPILE
1173// This is for testing purposes only!
1174void HashMap::HashMapTest()
1175{
1176 printf("HashMap test\n");
1177
1178 const unsigned int MinValue = 2; // Deleted is reserved, and is 1.
1179 const unsigned int MinThreshold = 10000;
1180 const unsigned int MaxThreshold = 30000;
1181 HashMap * table = new HashMap();
1182 Crst m_lock("HashMap", CrstSyncHashLock, CrstFlags(CRST_REENTRANCY | CRST_UNSAFE_ANYMODE));
1183 CrstHolder holder(&m_lock);
1184 LockOwner lock = {&m_lock, IsOwnerOfCrst};
1185 table->Init(10, (CompareFnPtr) NULL, false, &lock);
1186 for(unsigned int i=MinValue; i < MinThreshold; i++)
1187 table->InsertValue(i, i);
1188 printf("Added %d values.\n", MinThreshold);
1189 //table.DumpStatistics();
1190
1191 LookupPerfTest(table, MinThreshold);
1192
1193 INT64 t0 = GetTickCount();
1194 INT64 t1;
1195 for(int rep = 0; rep < 10000000; rep++) {
1196 for(unsigned int i=MinThreshold; i < MaxThreshold; i++) {
1197 table->InsertValue(rep + i, rep + i);
1198 }
1199 for(unsigned int i=MinThreshold; i < MaxThreshold; i++) {
1200 table->DeleteValue(rep + i, rep + i);
1201 }
1202 for(unsigned int i=MinValue; i < MinThreshold; i++)
1203 table->DeleteValue(i, i);
1204 for(unsigned int i=MinValue; i < MinThreshold; i++)
1205 table->InsertValue(i, i);
1206
1207 if (rep % 500 == 0) {
1208 t1 = GetTickCount();
1209 printf("Repetition %d, took %d ms\n", rep, (int) (t1-t0));
1210 t0 = t1;
1211 LookupPerfTest(table, MinThreshold);
1212 //table.DumpStatistics();
1213 }
1214 }
1215 delete table;
1216}
1217
1218// For testing purposes only.
1219void HashMap::LookupPerfTest(HashMap * table, const unsigned int MinThreshold)
1220{
1221 INT64 t0 = GetTickCount();
1222 for(int rep = 0; rep < 1000; rep++) {
1223 for(unsigned int i=2; i<MinThreshold; i++) {
1224 UPTR v = table->LookupValue(i, i);
1225 if (v != i) {
1226 printf("LookupValue didn't return the expected value!");
1227 _ASSERTE(v == i);
1228 }
1229 }
1230 }
1231 INT64 t1 = GetTickCount();
1232 for(unsigned int i = MinThreshold * 80; i < MinThreshold * 80 + 1000; i++)
1233 table->LookupValue(i, i);
1234 //cout << "Lookup perf test (1000 * " << MinThreshold << ": " << (t1-t0) << " ms." << endl;
1235#ifdef HASHTABLE_PROFILE
1236 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);
1237 table->DumpStatistics();
1238#else // !HASHTABLE_PROFILE
1239 printf("Lookup perf test time: %d ms table size: %d\n", (int) (t1-t0), table->GetSize(table->Buckets()));
1240#endif // !HASHTABLE_PROFILE
1241}
1242#endif // !DACCESS_COMPILE
1243#endif // 0 // Perf test code, enabled on-demand for private testing.
1244