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#ifndef _EE_HASH_INL
8#define _EE_HASH_INL
9
10#ifdef _DEBUG_IMPL
11template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
12BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::OwnLock()
13{
14 WRAPPER_NO_CONTRACT;
15 if (m_CheckThreadSafety == FALSE)
16 return TRUE;
17
18 if (m_pfnLockOwner == NULL) {
19 return m_writerThreadId.IsCurrentThread();
20 }
21 else {
22 BOOL ret = m_pfnLockOwner(m_lockData);
23 if (!ret) {
24 if (Debug_IsLockedViaThreadSuspension()) {
25 ret = TRUE;
26 }
27 }
28 return ret;
29 }
30}
31#endif // _DEBUG_IMPL
32
33#ifndef DACCESS_COMPILE
34template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
35void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::Destroy()
36{
37 CONTRACTL
38 {
39 WRAPPER(THROWS);
40 WRAPPER(GC_NOTRIGGER);
41 FORBID_FAULT;
42 }
43 CONTRACTL_END
44
45 if (m_pVolatileBucketTable && m_pVolatileBucketTable->m_pBuckets != NULL)
46 {
47 DWORD i;
48
49 for (i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++)
50 {
51 EEHashEntry_t *pEntry, *pNext;
52
53 for (pEntry = m_pVolatileBucketTable->m_pBuckets[i]; pEntry != NULL; pEntry = pNext)
54 {
55 pNext = pEntry->pNext;
56 Helper::DeleteEntry(pEntry, m_Heap);
57 }
58 }
59
60 delete[] (m_pVolatileBucketTable->m_pBuckets-1);
61
62 m_pVolatileBucketTable = NULL;
63 }
64
65}
66
67template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
68void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::ClearHashTable()
69{
70 CONTRACTL
71 {
72 WRAPPER(THROWS);
73 WRAPPER(GC_NOTRIGGER);
74 FORBID_FAULT;
75 }
76 CONTRACTL_END
77
78 //_ASSERTE (OwnLock());
79
80 // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read
81 // from multiple threads without taking locks. On rehash, you want to get rid of the old copy
82 // of table. You can only get rid of it once nobody is using it. That's a problem because
83 // there is no lock to tell when the last reader stopped using the old copy of the table.
84 // The solution to this problem is to access the table in cooperative mode, and to get rid of
85 // the old copy of the table when we are suspended for GC. When we are suspended for GC,
86 // we know that nobody is using the old copy of the table anymore.
87 // BROKEN: This is called sometimes from the CorMap hash before the EE is started up
88 GCX_COOP_NO_THREAD_BROKEN();
89
90 if (m_pVolatileBucketTable->m_pBuckets != NULL)
91 {
92 DWORD i;
93
94 for (i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++)
95 {
96 EEHashEntry_t *pEntry, *pNext;
97
98 for (pEntry = m_pVolatileBucketTable->m_pBuckets[i]; pEntry != NULL; pEntry = pNext)
99 {
100 pNext = pEntry->pNext;
101 Helper::DeleteEntry(pEntry, m_Heap);
102 }
103 }
104
105 delete[] (m_pVolatileBucketTable->m_pBuckets-1);
106 m_pVolatileBucketTable->m_pBuckets = NULL;
107 }
108
109 m_pVolatileBucketTable->m_dwNumBuckets = 0;
110 m_dwNumEntries = 0;
111}
112
113template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
114void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::EmptyHashTable()
115{
116 CONTRACTL
117 {
118 WRAPPER(THROWS);
119 WRAPPER(GC_NOTRIGGER);
120 FORBID_FAULT;
121 }
122 CONTRACTL_END
123
124 _ASSERTE (OwnLock());
125
126 // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read
127 // from multiple threads without taking locks. On rehash, you want to get rid of the old copy
128 // of table. You can only get rid of it once nobody is using it. That's a problem because
129 // there is no lock to tell when the last reader stopped using the old copy of the table.
130 // The solution to this problem is to access the table in cooperative mode, and to get rid of
131 // the old copy of the table when we are suspended for GC. When we are suspended for GC,
132 // we know that nobody is using the old copy of the table anymore.
133 // BROKEN: This is called sometimes from the CorMap hash before the EE is started up
134 GCX_COOP_NO_THREAD_BROKEN();
135
136 if (m_pVolatileBucketTable->m_pBuckets != NULL)
137 {
138 DWORD i;
139
140 for (i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++)
141 {
142 EEHashEntry_t *pEntry, *pNext;
143
144 for (pEntry = m_pVolatileBucketTable->m_pBuckets[i]; pEntry != NULL; pEntry = pNext)
145 {
146 pNext = pEntry->pNext;
147 Helper::DeleteEntry(pEntry, m_Heap);
148 }
149
150 m_pVolatileBucketTable->m_pBuckets[i] = NULL;
151 }
152 }
153
154 m_dwNumEntries = 0;
155}
156
157template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
158
159BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::Init(DWORD dwNumBuckets, LockOwner *pLock, AllocationHeap pHeap, BOOL CheckThreadSafety)
160{
161 CONTRACTL
162 {
163 WRAPPER(NOTHROW);
164 WRAPPER(GC_NOTRIGGER);
165 INJECT_FAULT(return FALSE;);
166
167#ifndef DACCESS_COMPILE
168 PRECONDITION(m_pVolatileBucketTable.Load() == NULL && "EEHashTable::Init() called twice.");
169#endif
170
171 }
172 CONTRACTL_END
173
174 m_pVolatileBucketTable = &m_BucketTable[0];
175
176 DWORD dwNumBucketsPlusOne;
177
178 // Prefast overflow sanity check the addition
179 if (!ClrSafeInt<DWORD>::addition(dwNumBuckets, 1, dwNumBucketsPlusOne))
180 return FALSE;
181
182 S_SIZE_T safeSize(sizeof(EEHashEntry_t *));
183 safeSize *= dwNumBucketsPlusOne;
184 if (safeSize.IsOverflow())
185 ThrowHR(COR_E_OVERFLOW);
186 SIZE_T cbAlloc = safeSize.Value();
187
188 m_pVolatileBucketTable->m_pBuckets = (EEHashEntry_t **) new (nothrow) BYTE[cbAlloc];
189
190 if (m_pVolatileBucketTable->m_pBuckets == NULL)
191 return FALSE;
192
193 memset(m_pVolatileBucketTable->m_pBuckets, 0, cbAlloc);
194
195 // The first slot links to the next list.
196 m_pVolatileBucketTable->m_pBuckets++;
197
198 m_pVolatileBucketTable->m_dwNumBuckets = dwNumBuckets;
199
200 m_Heap = pHeap;
201
202#ifdef _DEBUG
203 if (pLock == NULL) {
204 m_lockData = NULL;
205 m_pfnLockOwner = NULL;
206 }
207 else {
208 m_lockData = pLock->lock;
209 m_pfnLockOwner = pLock->lockOwnerFunc;
210 }
211
212 if (m_pfnLockOwner == NULL) {
213 m_writerThreadId.SetToCurrentThread();
214 }
215 m_CheckThreadSafety = CheckThreadSafety;
216#endif
217
218 return TRUE;
219}
220
221
222// Does not handle duplicates!
223
224template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
225void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::InsertValue(KeyType pKey, HashDatum Data, BOOL bDeepCopyKey)
226{
227 CONTRACTL
228 {
229 WRAPPER(THROWS);
230 WRAPPER(GC_NOTRIGGER);
231 INJECT_FAULT(COMPlusThrowOM(););
232 }
233 CONTRACTL_END
234
235 _ASSERTE (OwnLock());
236
237 // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read
238 // from multiple threads without taking locks. On rehash, you want to get rid of the old copy
239 // of table. You can only get rid of it once nobody is using it. That's a problem because
240 // there is no lock to tell when the last reader stopped using the old copy of the table.
241 // The solution to this problem is to access the table in cooperative mode, and to get rid of
242 // the old copy of the table when we are suspended for GC. When we are suspended for GC,
243 // we know that nobody is using the old copy of the table anymore.
244 // BROKEN: This is called sometimes from the CorMap hash before the EE is started up
245 GCX_COOP_NO_THREAD_BROKEN();
246
247 _ASSERTE(m_pVolatileBucketTable->m_dwNumBuckets != 0);
248
249 if (m_dwNumEntries > m_pVolatileBucketTable->m_dwNumBuckets*2)
250 {
251 if (!GrowHashTable()) COMPlusThrowOM();
252 }
253
254 DWORD dwHash = (DWORD)Helper::Hash(pKey);
255 DWORD dwBucket = dwHash % m_pVolatileBucketTable->m_dwNumBuckets;
256 EEHashEntry_t * pNewEntry;
257
258 pNewEntry = Helper::AllocateEntry(pKey, bDeepCopyKey, m_Heap);
259 if (!pNewEntry)
260 {
261 COMPlusThrowOM();
262 }
263
264 // Fill in the information for the new entry.
265 pNewEntry->pNext = m_pVolatileBucketTable->m_pBuckets[dwBucket];
266 pNewEntry->Data = Data;
267 pNewEntry->dwHashValue = dwHash;
268
269 // Insert at head of bucket
270 // need volatile write to avoid write reordering problem in IA
271 VolatileStore(&m_pVolatileBucketTable->m_pBuckets[dwBucket], pNewEntry);;
272
273 m_dwNumEntries++;
274}
275
276
277// Similar to the above, except that the HashDatum is a pointer to key.
278template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
279void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::InsertKeyAsValue(KeyType pKey, BOOL bDeepCopyKey)
280{
281 CONTRACTL
282 {
283 WRAPPER(THROWS);
284 WRAPPER(GC_NOTRIGGER);
285 INJECT_FAULT(COMPlusThrowOM(););
286 }
287 CONTRACTL_END
288
289 _ASSERTE (OwnLock());
290
291 // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read
292 // from multiple threads without taking locks. On rehash, you want to get rid of the old copy
293 // of table. You can only get rid of it once nobody is using it. That's a problem because
294 // there is no lock to tell when the last reader stopped using the old copy of the table.
295 // The solution to this problem is to access the table in cooperative mode, and to get rid of
296 // the old copy of the table when we are suspended for GC. When we are suspended for GC,
297 // we know that nobody is using the old copy of the table anymore.
298 // BROKEN: This is called sometimes from the CorMap hash before the EE is started up
299 GCX_COOP_NO_THREAD_BROKEN();
300
301 _ASSERTE(m_pVolatileBucketTable->m_dwNumBuckets != 0);
302
303 if (m_dwNumEntries > m_pVolatileBucketTable->m_dwNumBuckets*2)
304 {
305 if (!GrowHashTable()) COMPlusThrowOM();
306 }
307
308 DWORD dwHash = Helper::Hash(pKey);
309 DWORD dwBucket = dwHash % m_pVolatileBucketTable->m_dwNumBuckets;
310 EEHashEntry_t * pNewEntry;
311
312 pNewEntry = Helper::AllocateEntry(pKey, bDeepCopyKey, m_Heap);
313 if (!pNewEntry)
314 {
315 COMPlusThrowOM();
316 }
317
318 // Fill in the information for the new entry.
319 pNewEntry->pNext = m_pVolatileBucketTable->m_pBuckets[dwBucket];
320 pNewEntry->dwHashValue = dwHash;
321 pNewEntry->Data = *((LPUTF8 *)pNewEntry->Key);
322
323 // Insert at head of bucket
324 // need volatile write to avoid write reordering problem in IA
325 VolatileStore(&m_pVolatileBucketTable->m_pBuckets[dwBucket], pNewEntry);
326
327 m_dwNumEntries++;
328}
329
330
331template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
332BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::DeleteValue(KeyType pKey)
333{
334 CONTRACTL
335 {
336 WRAPPER(THROWS);
337 WRAPPER(GC_NOTRIGGER);
338 FORBID_FAULT;
339 }
340 CONTRACTL_END
341
342 _ASSERTE (OwnLock());
343
344 Thread *pThread = GetThreadNULLOk();
345 GCX_MAYBE_COOP_NO_THREAD_BROKEN(pThread ? !(pThread->m_StateNC & Thread::TSNC_UnsafeSkipEnterCooperative) : FALSE);
346
347 _ASSERTE(m_pVolatileBucketTable->m_dwNumBuckets != 0);
348
349 DWORD dwHash = Helper::Hash(pKey);
350 DWORD dwBucket = dwHash % m_pVolatileBucketTable->m_dwNumBuckets;
351 EEHashEntry_t * pSearch;
352 EEHashEntry_t **ppPrev = &m_pVolatileBucketTable->m_pBuckets[dwBucket];
353
354 for (pSearch = m_pVolatileBucketTable->m_pBuckets[dwBucket]; pSearch; pSearch = pSearch->pNext)
355 {
356 if (pSearch->dwHashValue == dwHash && Helper::CompareKeys(pSearch, pKey))
357 {
358 *ppPrev = pSearch->pNext;
359 Helper::DeleteEntry(pSearch, m_Heap);
360
361 // Do we ever want to shrink?
362 m_dwNumEntries--;
363
364 return TRUE;
365 }
366
367 ppPrev = &pSearch->pNext;
368 }
369
370 return FALSE;
371}
372
373
374template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
375BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::ReplaceValue(KeyType pKey, HashDatum Data)
376{
377 CONTRACTL
378 {
379 WRAPPER(THROWS);
380 WRAPPER(GC_NOTRIGGER);
381 FORBID_FAULT;
382 }
383 CONTRACTL_END
384
385 _ASSERTE (OwnLock());
386
387 EEHashEntry_t *pItem = FindItem(pKey);
388
389 if (pItem != NULL)
390 {
391 // Required to be atomic
392 pItem->Data = Data;
393 return TRUE;
394 }
395 else
396 {
397 return FALSE;
398 }
399}
400
401
402template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
403BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::ReplaceKey(KeyType pOldKey, KeyType pNewKey)
404{
405 CONTRACTL
406 {
407 WRAPPER(THROWS);
408 WRAPPER(GC_NOTRIGGER);
409 FORBID_FAULT;
410 }
411 CONTRACTL_END
412
413 _ASSERTE (OwnLock());
414
415 EEHashEntry_t *pItem = FindItem(pOldKey);
416
417 if (pItem != NULL)
418 {
419 Helper::ReplaceKey (pItem, pNewKey);
420 return TRUE;
421 }
422 else
423 {
424 return FALSE;
425 }
426}
427#endif // !DACCESS_COMPILE
428
429template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
430DWORD EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetHash(KeyType pKey)
431{
432 WRAPPER_NO_CONTRACT;
433 return Helper::Hash(pKey);
434}
435
436
437template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
438BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetValue(KeyType pKey, HashDatum *pData)
439{
440 CONTRACTL
441 {
442 WRAPPER(THROWS);
443 WRAPPER(GC_NOTRIGGER);
444 FORBID_FAULT;
445 SO_TOLERANT;
446 SUPPORTS_DAC;
447 }
448 CONTRACTL_END
449
450 EEHashEntry_t *pItem = FindItem(pKey);
451
452 if (pItem != NULL)
453 {
454 *pData = pItem->Data;
455 return TRUE;
456 }
457 else
458 {
459 return FALSE;
460 }
461}
462
463template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
464BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetValue(KeyType pKey, HashDatum *pData, DWORD hashValue)
465{
466 CONTRACTL
467 {
468 WRAPPER(THROWS);
469 WRAPPER(GC_NOTRIGGER);
470 FORBID_FAULT;
471 }
472 CONTRACTL_END
473
474 EEHashEntry_t *pItem = FindItem(pKey, hashValue);
475
476 if (pItem != NULL)
477 {
478 *pData = pItem->Data;
479 return TRUE;
480 }
481 else
482 {
483 return FALSE;
484 }
485}
486
487template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
488FORCEINLINE BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetValueSpeculative(KeyType pKey, HashDatum *pData)
489{
490 CONTRACTL
491 {
492 WRAPPER(THROWS);
493 WRAPPER(GC_NOTRIGGER);
494#ifdef MODE_COOPERATIVE // This header file sees contract.h, not eecontract.h - what a kludge!
495 MODE_COOPERATIVE;
496#endif
497 SO_TOLERANT;
498 }
499 CONTRACTL_END
500
501 EEHashEntry_t *pItem = FindItemSpeculative(pKey, Helper::Hash(pKey));
502
503 if (pItem != NULL)
504 {
505 *pData = pItem->Data;
506 return TRUE;
507 }
508 else
509 {
510 return FALSE;
511 }
512}
513
514template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
515EEHashEntry_t *EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::FindItem(KeyType pKey)
516{
517 CONTRACTL
518 {
519 WRAPPER(THROWS);
520 WRAPPER(GC_NOTRIGGER);
521 FORBID_FAULT;
522 SO_TOLERANT;
523 SUPPORTS_DAC;
524 }
525 CONTRACTL_END
526
527 return FindItem(pKey, Helper::Hash(pKey));
528}
529
530template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
531EEHashEntry_t *EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::FindItem(KeyType pKey, DWORD dwHash)
532{
533 CONTRACTL
534 {
535 WRAPPER(THROWS);
536 WRAPPER(GC_NOTRIGGER);
537 FORBID_FAULT;
538 SO_TOLERANT;
539 SUPPORTS_DAC;
540 }
541 CONTRACTL_END
542
543 // Transition to COOP mode. This is need because EEHashTable is lock free and it can be read
544 // from multiple threads without taking locks. On rehash, you want to get rid of the old copy
545 // of table. You can only get rid of it once nobody is using it. That's a problem because
546 // there is no lock to tell when the last reader stopped using the old copy of the table.
547 // The solution to this problem is to access the table in cooperative mode, and to get rid of
548 // the old copy of the table when we are suspended for GC. When we are suspended for GC,
549 // we know that nobody is using the old copy of the table anymore.
550 //
551#ifndef DACCESS_COMPILE
552 GCX_COOP_NO_THREAD_BROKEN();
553#endif
554
555 // Atomic transaction. In any other point of this method or ANY of the callees of this function you can not read
556 // from m_pVolatileBucketTable!!!!!!! A racing condition would occur.
557 DWORD dwOldNumBuckets;
558
559#ifndef DACCESS_COMPILE
560 DWORD nTry = 0;
561 DWORD dwSwitchCount = 0;
562#endif
563
564 do
565 {
566 BucketTable* pBucketTable=(BucketTable*)(PTR_BucketTable)m_pVolatileBucketTable.Load();
567 dwOldNumBuckets = pBucketTable->m_dwNumBuckets;
568
569 _ASSERTE(pBucketTable->m_dwNumBuckets != 0);
570
571 DWORD dwBucket = dwHash % pBucketTable->m_dwNumBuckets;
572 EEHashEntry_t * pSearch;
573
574 for (pSearch = pBucketTable->m_pBuckets[dwBucket]; pSearch; pSearch = pSearch->pNext)
575 {
576 if (pSearch->dwHashValue == dwHash && Helper::CompareKeys(pSearch, pKey))
577 return pSearch;
578 }
579
580 // There is a race in EEHash Table: when we grow the hash table, we will nuke out
581 // the old bucket table. Readers might be looking up in the old table, they can
582 // fail to find an existing entry. The workaround is to retry the search process
583 // if we are called grow table during the search process.
584#ifndef DACCESS_COMPILE
585 nTry ++;
586 if (nTry == 20) {
587 __SwitchToThread(0, ++dwSwitchCount);
588 nTry = 0;
589 }
590#endif // #ifndef DACCESS_COMPILE
591 }
592 while ( m_bGrowing || dwOldNumBuckets != m_pVolatileBucketTable->m_dwNumBuckets);
593
594 return NULL;
595}
596
597template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
598FORCEINLINE EEHashEntry_t *EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::FindItemSpeculative(KeyType pKey, DWORD dwHash)
599{
600 CONTRACTL
601 {
602 WRAPPER(THROWS);
603 WRAPPER(GC_NOTRIGGER);
604#ifdef MODE_COOPERATIVE // This header file sees contract.h, not eecontract.h - what a kludge!
605 MODE_COOPERATIVE;
606#endif
607 SO_TOLERANT;
608 }
609 CONTRACTL_END
610
611 // Atomic transaction. In any other point of this method or ANY of the callees of this function you can not read
612 // from m_pVolatileBucketTable!!!!!!! A racing condition would occur.
613 DWORD dwOldNumBuckets;
614
615 BucketTable* pBucketTable=m_pVolatileBucketTable;
616 dwOldNumBuckets = pBucketTable->m_dwNumBuckets;
617
618 _ASSERTE(pBucketTable->m_dwNumBuckets != 0);
619
620 DWORD dwBucket = dwHash % pBucketTable->m_dwNumBuckets;
621 EEHashEntry_t * pSearch;
622
623 for (pSearch = pBucketTable->m_pBuckets[dwBucket]; pSearch; pSearch = pSearch->pNext)
624 {
625 if (pSearch->dwHashValue == dwHash && Helper::CompareKeys(pSearch, pKey))
626 return pSearch;
627 }
628
629 return NULL;
630}
631
632template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
633BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::IsEmpty()
634{
635 LIMITED_METHOD_CONTRACT;
636 return m_dwNumEntries == 0;
637}
638
639template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
640DWORD EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GetCount()
641{
642 LIMITED_METHOD_CONTRACT;
643 return m_dwNumEntries;
644}
645
646#ifndef DACCESS_COMPILE
647
648template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
649BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::GrowHashTable()
650{
651 CONTRACTL
652 {
653 WRAPPER(THROWS);
654 WRAPPER(GC_NOTRIGGER);
655 INJECT_FAULT(return FALSE;);
656 }
657 CONTRACTL_END
658
659#if defined(_DEBUG) && !defined(CROSSGEN_COMPILE)
660 BEGIN_GETTHREAD_ALLOWED;
661 Thread * pThread = GetThread();
662 _ASSERTE(!g_fEEStarted || (pThread == NULL) || (pThread->PreemptiveGCDisabled()));
663 END_GETTHREAD_ALLOWED;
664#endif
665
666 // Make the new bucket table 4 times bigger
667 //
668 DWORD dwNewNumBuckets;
669 DWORD dwNewNumBucketsPlusOne;
670 {
671 S_UINT32 safeSize(m_pVolatileBucketTable->m_dwNumBuckets);
672
673 safeSize *= 4;
674
675 if (safeSize.IsOverflow())
676 return FALSE;
677
678 dwNewNumBuckets = safeSize.Value();
679
680 safeSize += 1; // Allocate one extra
681
682 if (safeSize.IsOverflow())
683 return FALSE;
684
685 dwNewNumBucketsPlusOne = safeSize.Value();
686 }
687
688 // On resizes, we still have an array of old pointers we need to worry about.
689 // We can't free these old pointers, for we may hit a race condition where we're
690 // resizing and reading from the array at the same time. We need to keep track of these
691 // old arrays of pointers, so we're going to use the last item in the array to "link"
692 // to previous arrays, so that they may be freed at the end.
693 //
694
695 SIZE_T cbAlloc;
696 {
697 S_SIZE_T safeSize(sizeof(EEHashEntry_t *));
698
699 safeSize *= dwNewNumBucketsPlusOne;
700
701 if (safeSize.IsOverflow())
702 return FALSE;
703
704 cbAlloc = safeSize.Value();
705 }
706
707 EEHashEntry_t **pNewBuckets = (EEHashEntry_t **) new (nothrow) BYTE[cbAlloc];
708
709 if (pNewBuckets == NULL)
710 return FALSE;
711
712 memset(pNewBuckets, 0, cbAlloc);
713
714 // The first slot is linked to next list.
715 pNewBuckets++;
716
717 // Run through the old table and transfer all the entries
718
719 // Be sure not to mess with the integrity of the old table while
720 // we are doing this, as there can be concurrent readers! Note that
721 // it is OK if the concurrent reader misses out on a match, though -
722 // they will have to acquire the lock on a miss & try again.
723 FastInterlockExchange( (LONG *) &m_bGrowing, 1);
724 for (DWORD i = 0; i < m_pVolatileBucketTable->m_dwNumBuckets; i++)
725 {
726 EEHashEntry_t * pEntry = m_pVolatileBucketTable->m_pBuckets[i];
727
728 // Try to lock out readers from scanning this bucket. This is
729 // obviously a race which may fail. However, note that it's OK
730 // if somebody is already in the list - it's OK if we mess
731 // with the bucket groups, as long as we don't destroy
732 // anything. The lookup function will still do appropriate
733 // comparison even if it wanders aimlessly amongst entries
734 // while we are rearranging things. If a lookup finds a match
735 // under those circumstances, great. If not, they will have
736 // to acquire the lock & try again anyway.
737
738 m_pVolatileBucketTable->m_pBuckets[i] = NULL;
739
740 while (pEntry != NULL)
741 {
742 DWORD dwNewBucket = pEntry->dwHashValue % dwNewNumBuckets;
743 EEHashEntry_t * pNextEntry = pEntry->pNext;
744
745 pEntry->pNext = pNewBuckets[dwNewBucket];
746 pNewBuckets[dwNewBucket] = pEntry;
747 pEntry = pNextEntry;
748 }
749 }
750
751
752 // Finally, store the new number of buckets and the new bucket table
753 BucketTable* pNewBucketTable = (m_pVolatileBucketTable == &m_BucketTable[0]) ?
754 &m_BucketTable[1]:
755 &m_BucketTable[0];
756
757 pNewBucketTable->m_pBuckets = pNewBuckets;
758 pNewBucketTable->m_dwNumBuckets = dwNewNumBuckets;
759
760 // Add old table to the to free list. Note that the SyncClean thing will only
761 // delete the buckets at a safe point
762 //
763 SyncClean::AddEEHashTable (m_pVolatileBucketTable->m_pBuckets);
764
765 // Note that the SyncClean:AddEEHashTable performs at least one Interlock operation
766 // So we do not need to use an Interlocked operation to write m_pVolatileBucketTable
767 // Swap the double buffer, this is an atomic operation (the assignment)
768 //
769 m_pVolatileBucketTable = pNewBucketTable;
770
771 FastInterlockExchange( (LONG *) &m_bGrowing, 0);
772
773 return TRUE;
774}
775
776#endif // DACCESS_COMPILE
777
778// Walk through all the entries in the hash table, in meaningless order, without any
779// synchronization.
780//
781// IterateStart()
782// while (IterateNext())
783// GetKey();
784//
785template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
786void EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::
787 IterateStart(EEHashTableIteration *pIter)
788{
789 CONTRACTL
790 {
791 WRAPPER(THROWS);
792 WRAPPER(GC_NOTRIGGER);
793 FORBID_FAULT;
794 }
795 CONTRACTL_END
796
797 _ASSERTE_IMPL(OwnLock());
798 pIter->m_dwBucket = -1;
799 pIter->m_pEntry = NULL;
800
801#ifdef _DEBUG
802 pIter->m_pTable = this;
803#endif
804}
805
806template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
807BOOL EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::
808 IterateNext(EEHashTableIteration *pIter)
809{
810 CONTRACTL
811 {
812 WRAPPER(THROWS);
813 WRAPPER(GC_NOTRIGGER);
814 FORBID_FAULT;
815 }
816 CONTRACTL_END
817
818 _ASSERTE_IMPL(OwnLock());
819
820 Thread *pThread = GetThreadNULLOk();
821 GCX_MAYBE_COOP_NO_THREAD_BROKEN(pThread ? !(pThread->m_StateNC & Thread::TSNC_UnsafeSkipEnterCooperative) : FALSE);
822
823 _ASSERTE(pIter->m_pTable == (void *) this);
824
825 // If we haven't started iterating yet, or if we are at the end of a particular
826 // chain, advance to the next chain.
827 while (pIter->m_pEntry == NULL || pIter->m_pEntry->pNext == NULL)
828 {
829 if (++pIter->m_dwBucket >= m_pVolatileBucketTable->m_dwNumBuckets)
830 {
831 // advanced beyond the end of the table.
832 _ASSERTE(pIter->m_dwBucket == m_pVolatileBucketTable->m_dwNumBuckets); // client keeps asking?
833 return FALSE;
834 }
835 pIter->m_pEntry = m_pVolatileBucketTable->m_pBuckets[pIter->m_dwBucket];
836
837 // If this bucket has no chain, keep advancing. Otherwise we are done
838 if (pIter->m_pEntry)
839 return TRUE;
840 }
841
842 // We are within a chain. Advance to the next entry
843 pIter->m_pEntry = pIter->m_pEntry->pNext;
844
845 _ASSERTE(pIter->m_pEntry);
846 return TRUE;
847}
848
849template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
850KeyType EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::
851 IterateGetKey(EEHashTableIteration *pIter)
852{
853 CONTRACTL
854 {
855 WRAPPER(THROWS);
856 WRAPPER(GC_NOTRIGGER);
857 FORBID_FAULT;
858 }
859 CONTRACTL_END
860
861 _ASSERTE(pIter->m_pTable == (void *) this);
862 _ASSERTE(pIter->m_dwBucket < m_pVolatileBucketTable->m_dwNumBuckets && pIter->m_pEntry);
863 return Helper::GetKey(pIter->m_pEntry);
864}
865
866template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
867HashDatum EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>::
868 IterateGetValue(EEHashTableIteration *pIter)
869{
870 LIMITED_METHOD_CONTRACT;
871
872 _ASSERTE(pIter->m_pTable == (void *) this);
873 _ASSERTE(pIter->m_dwBucket < m_pVolatileBucketTable->m_dwNumBuckets && pIter->m_pEntry);
874 return pIter->m_pEntry->Data;
875}
876
877#endif /* _EE_HASH_INL */
878