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//emp
8// File: eehash.h
9//
10// Provides hash table functionality needed in the EE - intended to be replaced later with better
11// algorithms, but which have the same interface.
12//
13// Two requirements are:
14//
15// 1. Any number of threads can be reading the hash table while another thread is writing, without error.
16// 2. Only one thread can write at a time.
17// 3. When calling ReplaceValue(), a reader will get the old value, or the new value, but not something
18// in between.
19// 4. DeleteValue() is an unsafe operation - no other threads can be in the hash table when this happens.
20//
21
22#ifndef _EE_HASH_H
23#define _EE_HASH_H
24
25#include "exceptmacros.h"
26#include "syncclean.hpp"
27#ifdef FEATURE_PREJIT
28class DataImage;
29#endif
30
31#include "util.hpp"
32
33#ifdef FEATURE_PREJIT
34#include "corcompile.h"
35#endif
36
37class AllocMemTracker;
38class ClassLoader;
39struct LockOwner;
40class NameHandle;
41class SigTypeContext;
42
43// The "blob" you get to store in the hash table
44
45typedef PTR_VOID HashDatum;
46
47// The heap that you want the allocation to be done in
48
49typedef void* AllocationHeap;
50
51
52// One of these is present for each element in the table.
53// Update the SIZEOF_EEHASH_ENTRY macro below if you change this
54// struct
55
56typedef struct EEHashEntry EEHashEntry_t;
57typedef DPTR(EEHashEntry_t) PTR_EEHashEntry_t;
58struct EEHashEntry
59{
60 PTR_EEHashEntry_t pNext;
61 DWORD dwHashValue;
62 HashDatum Data;
63 BYTE Key[1]; // The key is stored inline
64};
65
66// The key[1] is a place holder for the key
67// SIZEOF_EEHASH_ENTRY is the size of struct up to (and not including) the key
68#define SIZEOF_EEHASH_ENTRY (offsetof(EEHashEntry,Key[0]))
69
70
71// Struct to hold a client's iteration state
72struct EEHashTableIteration;
73
74class GCHeap;
75
76// Generic hash table.
77
78template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
79class EEHashTableBase
80{
81public:
82
83
84 BOOL Init(DWORD dwNumBuckets, LockOwner *pLock, AllocationHeap pHeap = 0,BOOL CheckThreadSafety = TRUE);
85
86 void InsertValue(KeyType pKey, HashDatum Data, BOOL bDeepCopyKey = bDefaultCopyIsDeep);
87 void InsertKeyAsValue(KeyType pKey, BOOL bDeepCopyKey = bDefaultCopyIsDeep);
88 BOOL DeleteValue(KeyType pKey);
89 BOOL ReplaceValue(KeyType pKey, HashDatum Data);
90 BOOL ReplaceKey(KeyType pOldKey, KeyType pNewKey);
91 void ClearHashTable();
92 void EmptyHashTable();
93 BOOL IsEmpty();
94 void Destroy();
95
96 // Reader functions. Please place any functions that can be called from the
97 // reader threads here.
98 BOOL GetValue(KeyType pKey, HashDatum *pData);
99 BOOL GetValue(KeyType pKey, HashDatum *pData, DWORD hashValue);
100
101
102 // A fast inlinable flavor of GetValue that can return false instead of the actual item
103 // if there is race with updating of the hashtable. Callers of GetValueSpeculative
104 // should fall back to the slow GetValue if GetValueSpeculative returns false.
105 // Assumes that we are in cooperative mode already. For performance-sensitive codepaths.
106 BOOL GetValueSpeculative(KeyType pKey, HashDatum *pData);
107
108 DWORD GetHash(KeyType Key);
109 DWORD GetCount();
110
111 // Walk through all the entries in the hash table, in meaningless order, without any
112 // synchronization.
113 //
114 // IterateStart()
115 // while (IterateNext())
116 // IterateGetKey();
117 //
118 // This is guaranteed to be DeleteValue-friendly if you advance the iterator before
119 // deletig, i.e. if used in the following pattern:
120 //
121 // IterateStart();
122 // BOOL keepGoing = IterateNext();
123 // while(keepGoing)
124 // {
125 // key = IterateGetKey();
126 // keepGoing = IterateNext();
127 // ...
128 // DeleteValue(key);
129 // ..
130 // }
131 void IterateStart(EEHashTableIteration *pIter);
132 BOOL IterateNext(EEHashTableIteration *pIter);
133 KeyType IterateGetKey(EEHashTableIteration *pIter);
134 HashDatum IterateGetValue(EEHashTableIteration *pIter);
135#ifdef _DEBUG
136 void SuppressSyncCheck()
137 {
138 LIMITED_METHOD_CONTRACT;
139 m_CheckThreadSafety=FALSE;
140 }
141#endif
142protected:
143 BOOL GrowHashTable();
144 EEHashEntry_t * FindItem(KeyType pKey);
145 EEHashEntry_t * FindItem(KeyType pKey, DWORD hashValue);
146
147 // A fast inlinable flavor of FindItem that can return null instead of the actual item
148 // if there is race with updating of the hashtable. Callers of FindItemSpeculative
149 // should fall back to the slow FindItem if FindItemSpeculative returns null.
150 // Assumes that we are in cooperative mode already. For performance-sensitive codepaths.
151 EEHashEntry_t * FindItemSpeculative(KeyType pKey, DWORD hashValue);
152
153 // Double buffer to fix the race condition of growhashtable (the update
154 // of m_pBuckets and m_dwNumBuckets has to be atomic, so we double buffer
155 // the structure and access it through a pointer, which can be updated
156 // atomically. The union is in order to not change the SOS macros.
157
158 struct BucketTable
159 {
160 DPTR(PTR_EEHashEntry_t) m_pBuckets; // Pointer to first entry for each bucket
161 DWORD m_dwNumBuckets;
162 } m_BucketTable[2];
163 typedef DPTR(BucketTable) PTR_BucketTable;
164
165 // In a function we MUST only read this value ONCE, as the writer thread can change
166 // the value asynchronously. We make this member volatile the compiler won't do copy propagation
167 // optimizations that can make this read happen more than once. Note that we only need
168 // this property for the readers. As they are the ones that can have
169 // this variable changed (note also that if the variable was enregistered we wouldn't
170 // have any problem)
171 // BE VERY CAREFUL WITH WHAT YOU DO WITH THIS VARIABLE AS USING IT BADLY CAN CAUSE
172 // RACING CONDITIONS
173 VolatilePtr<BucketTable, PTR_BucketTable> m_pVolatileBucketTable;
174
175
176 DWORD m_dwNumEntries;
177 AllocationHeap m_Heap;
178 Volatile<LONG> m_bGrowing;
179#ifdef _DEBUG
180 LPVOID m_lockData;
181 FnLockOwner m_pfnLockOwner;
182
183 EEThreadId m_writerThreadId;
184 BOOL m_CheckThreadSafety;
185
186#endif
187
188#ifdef _DEBUG_IMPL
189 // A thread must own a lock for a hash if it is a writer.
190 BOOL OwnLock();
191#endif // _DEBUG_IMPL
192};
193
194template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
195class EEHashTable : public EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>
196{
197public:
198 EEHashTable()
199 {
200 LIMITED_METHOD_CONTRACT;
201 this->m_BucketTable[0].m_pBuckets = NULL;
202 this->m_BucketTable[0].m_dwNumBuckets = 0;
203 this->m_BucketTable[1].m_pBuckets = NULL;
204 this->m_BucketTable[1].m_dwNumBuckets = 0;
205#ifndef DACCESS_COMPILE
206 this->m_pVolatileBucketTable = NULL;
207#endif
208 this->m_dwNumEntries = 0;
209 this->m_bGrowing = 0;
210#ifdef _DEBUG
211 this->m_lockData = NULL;
212 this->m_pfnLockOwner = NULL;
213#endif
214 }
215
216 ~EEHashTable()
217 {
218 WRAPPER_NO_CONTRACT;
219 this->Destroy();
220 }
221};
222
223/* to be used as static variable - no constructor/destructor, assumes zero
224 initialized memory */
225template <class KeyType, class Helper, BOOL bDefaultCopyIsDeep>
226class EEHashTableStatic : public EEHashTableBase<KeyType, Helper, bDefaultCopyIsDeep>
227{
228};
229
230class EEIntHashTableHelper
231{
232public:
233 static EEHashEntry_t *AllocateEntry(int iKey, BOOL bDeepCopy, AllocationHeap pHeap = 0)
234 {
235 CONTRACTL
236 {
237 WRAPPER(THROWS);
238 WRAPPER(GC_NOTRIGGER);
239 INJECT_FAULT(return NULL;);
240 }
241 CONTRACTL_END
242
243 _ASSERTE(!bDeepCopy && "Deep copy is not supported by the EEPtrHashTableHelper");
244
245 EEHashEntry_t *pEntry = (EEHashEntry_t *) new (nothrow) BYTE[SIZEOF_EEHASH_ENTRY + sizeof(int)];
246 if (!pEntry)
247 return NULL;
248 *((int*) pEntry->Key) = iKey;
249
250 return pEntry;
251 }
252
253 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap pHeap = 0)
254 {
255 LIMITED_METHOD_CONTRACT;
256
257 // Delete the entry.
258 delete [] (BYTE*) pEntry;
259 }
260
261 static BOOL CompareKeys(EEHashEntry_t *pEntry, int iKey)
262 {
263 LIMITED_METHOD_CONTRACT;
264
265 return *((int*)pEntry->Key) == iKey;
266 }
267
268 static DWORD Hash(int iKey)
269 {
270 LIMITED_METHOD_CONTRACT;
271
272 return (DWORD)iKey;
273 }
274
275 static int GetKey(EEHashEntry_t *pEntry)
276 {
277 LIMITED_METHOD_CONTRACT;
278
279 return *((int*) pEntry->Key);
280 }
281};
282typedef EEHashTable<int, EEIntHashTableHelper, FALSE> EEIntHashTable;
283
284typedef struct PtrPlusInt
285{
286 void* pValue;
287 int iValue;
288} *PPtrPlusInt;
289
290class EEPtrPlusIntHashTableHelper
291{
292public:
293 static EEHashEntry_t *AllocateEntry(PtrPlusInt ppiKey, BOOL bDeepCopy, AllocationHeap pHeap = 0)
294 {
295 CONTRACTL
296 {
297 WRAPPER(THROWS);
298 WRAPPER(GC_NOTRIGGER);
299 INJECT_FAULT(return NULL;);
300 }
301 CONTRACTL_END
302
303 _ASSERTE(!bDeepCopy && "Deep copy is not supported by the EEPtrPlusIntHashTableHelper");
304
305 EEHashEntry_t *pEntry = (EEHashEntry_t *) new (nothrow) BYTE[SIZEOF_EEHASH_ENTRY + sizeof(PtrPlusInt)];
306 if (!pEntry)
307 return NULL;
308 *((PPtrPlusInt) pEntry->Key) = ppiKey;
309
310 return pEntry;
311 }
312
313 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap pHeap = 0)
314 {
315 LIMITED_METHOD_CONTRACT;
316
317 // Delete the entry.
318 delete [] (BYTE*) pEntry;
319 }
320
321 static BOOL CompareKeys(EEHashEntry_t *pEntry, PtrPlusInt ppiKey)
322 {
323 LIMITED_METHOD_CONTRACT;
324
325 return (((PPtrPlusInt)pEntry->Key)->pValue == ppiKey.pValue) &&
326 (((PPtrPlusInt)pEntry->Key)->iValue == ppiKey.iValue);
327 }
328
329 static DWORD Hash(PtrPlusInt ppiKey)
330 {
331 LIMITED_METHOD_CONTRACT;
332
333 return (DWORD)ppiKey.iValue ^
334#ifdef _TARGET_X86_
335 (DWORD)(size_t) ppiKey.pValue;
336#else
337 // <TODO> IA64: Is this a good hashing mechanism on IA64?</TODO>
338 (DWORD)(((size_t) ppiKey.pValue) >> 3);
339#endif
340 }
341
342 static PtrPlusInt GetKey(EEHashEntry_t *pEntry)
343 {
344 LIMITED_METHOD_CONTRACT;
345
346 return *((PPtrPlusInt) pEntry->Key);
347 }
348};
349
350typedef EEHashTable<PtrPlusInt, EEPtrPlusIntHashTableHelper, FALSE> EEPtrPlusIntHashTable;
351
352// UTF8 string hash table. The UTF8 strings are NULL terminated.
353
354class EEUtf8HashTableHelper
355{
356public:
357 static EEHashEntry_t * AllocateEntry(LPCUTF8 pKey, BOOL bDeepCopy, AllocationHeap Heap);
358 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap);
359 static BOOL CompareKeys(EEHashEntry_t *pEntry, LPCUTF8 pKey);
360 static DWORD Hash(LPCUTF8 pKey);
361 static LPCUTF8 GetKey(EEHashEntry_t *pEntry);
362};
363
364typedef EEHashTable<LPCUTF8, EEUtf8HashTableHelper, TRUE> EEUtf8StringHashTable;
365typedef DPTR(EEUtf8StringHashTable) PTR_EEUtf8StringHashTable;
366
367// Unicode String hash table - the keys are UNICODE strings which may
368// contain embedded nulls. An EEStringData struct is used for the key
369// which contains the length of the item. Note that this string is
370// not necessarily null terminated and should never be treated as such.
371const DWORD ONLY_LOW_CHARS_MASK = 0x80000000;
372
373class EEStringData
374{
375private:
376 LPCWSTR szString; // The string data.
377 DWORD cch; // Characters in the string.
378#ifdef _DEBUG
379 BOOL bDebugOnlyLowChars; // Does the string contain only characters less than 0x80?
380 DWORD dwDebugCch;
381#endif // _DEBUG
382
383public:
384 // explicilty initialize cch to 0 because SetCharCount uses cch
385 EEStringData() : cch(0)
386 {
387 LIMITED_METHOD_CONTRACT;
388
389 SetStringBuffer(NULL);
390 SetCharCount(0);
391 SetIsOnlyLowChars(FALSE);
392 };
393 EEStringData(DWORD cchString, LPCWSTR str) : cch(0)
394 {
395 LIMITED_METHOD_CONTRACT;
396
397 SetStringBuffer(str);
398 SetCharCount(cchString);
399 SetIsOnlyLowChars(FALSE);
400 };
401 EEStringData(DWORD cchString, LPCWSTR str, BOOL onlyLow) : cch(0)
402 {
403 LIMITED_METHOD_CONTRACT;
404
405 SetStringBuffer(str);
406 SetCharCount(cchString);
407 SetIsOnlyLowChars(onlyLow);
408 };
409 inline ULONG GetCharCount() const
410 {
411 LIMITED_METHOD_CONTRACT;
412
413 _ASSERTE ((cch & ~ONLY_LOW_CHARS_MASK) == dwDebugCch);
414 return (cch & ~ONLY_LOW_CHARS_MASK);
415 }
416 inline void SetCharCount(ULONG _cch)
417 {
418 LIMITED_METHOD_CONTRACT;
419
420#ifdef _DEBUG
421 dwDebugCch = _cch;
422#endif // _DEBUG
423 cch = ((DWORD)_cch) | (cch & ONLY_LOW_CHARS_MASK);
424 }
425 inline LPCWSTR GetStringBuffer() const
426 {
427 LIMITED_METHOD_CONTRACT;
428
429 return (szString);
430 }
431 inline void SetStringBuffer(LPCWSTR _szString)
432 {
433 LIMITED_METHOD_CONTRACT;
434
435 szString = _szString;
436 }
437 inline BOOL GetIsOnlyLowChars() const
438 {
439 LIMITED_METHOD_CONTRACT;
440
441 _ASSERTE(bDebugOnlyLowChars == ((cch & ONLY_LOW_CHARS_MASK) ? TRUE : FALSE));
442 return ((cch & ONLY_LOW_CHARS_MASK) ? TRUE : FALSE);
443 }
444 inline void SetIsOnlyLowChars(BOOL bIsOnlyLowChars)
445 {
446 LIMITED_METHOD_CONTRACT;
447
448#ifdef _DEBUG
449 bDebugOnlyLowChars = bIsOnlyLowChars;
450#endif // _DEBUG
451 bIsOnlyLowChars ? (cch |= ONLY_LOW_CHARS_MASK) : (cch &= ~ONLY_LOW_CHARS_MASK);
452 }
453};
454
455class EEUnicodeHashTableHelper
456{
457public:
458 static EEHashEntry_t * AllocateEntry(EEStringData *pKey, BOOL bDeepCopy, AllocationHeap Heap);
459 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap);
460 static BOOL CompareKeys(EEHashEntry_t *pEntry, EEStringData *pKey);
461 static DWORD Hash(EEStringData *pKey);
462 static EEStringData * GetKey(EEHashEntry_t *pEntry);
463 static void ReplaceKey(EEHashEntry_t *pEntry, EEStringData *pNewKey);
464};
465
466typedef EEHashTable<EEStringData *, EEUnicodeHashTableHelper, TRUE> EEUnicodeStringHashTable;
467
468
469class EEUnicodeStringLiteralHashTableHelper
470{
471public:
472 static EEHashEntry_t * AllocateEntry(EEStringData *pKey, BOOL bDeepCopy, AllocationHeap Heap);
473 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap);
474 static BOOL CompareKeys(EEHashEntry_t *pEntry, EEStringData *pKey);
475 static DWORD Hash(EEStringData *pKey);
476 static void ReplaceKey(EEHashEntry_t *pEntry, EEStringData *pNewKey);
477};
478
479typedef EEHashTable<EEStringData *, EEUnicodeStringLiteralHashTableHelper, TRUE> EEUnicodeStringLiteralHashTable;
480
481
482// Generic pointer hash table helper.
483
484template <class KeyPointerType>
485class EEPtrHashTableHelper
486{
487public:
488 static EEHashEntry_t *AllocateEntry(KeyPointerType pKey, BOOL bDeepCopy, AllocationHeap Heap)
489 {
490 CONTRACTL
491 {
492 WRAPPER(THROWS);
493 WRAPPER(GC_NOTRIGGER);
494 INJECT_FAULT(return FALSE;);
495 }
496 CONTRACTL_END
497
498 _ASSERTE(!bDeepCopy && "Deep copy is not supported by the EEPtrHashTableHelper");
499 _ASSERTE(sizeof(KeyPointerType) == sizeof(void *) && "KeyPointerType must be a pointer type");
500
501 EEHashEntry_t *pEntry = (EEHashEntry_t *) new (nothrow) BYTE[SIZEOF_EEHASH_ENTRY + sizeof(KeyPointerType)];
502 if (!pEntry)
503 return NULL;
504 *((KeyPointerType*)pEntry->Key) = pKey;
505
506 return pEntry;
507 }
508
509 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap)
510 {
511 LIMITED_METHOD_CONTRACT;
512
513 // Delete the entry.
514 delete [] (BYTE*) pEntry;
515 }
516
517 static BOOL CompareKeys(EEHashEntry_t *pEntry, KeyPointerType pKey)
518 {
519 LIMITED_METHOD_CONTRACT;
520 SUPPORTS_DAC;
521
522 KeyPointerType pEntryKey = *((KeyPointerType*)pEntry->Key);
523 return pEntryKey == pKey;
524 }
525
526 static DWORD Hash(KeyPointerType pKey)
527 {
528 LIMITED_METHOD_CONTRACT;
529 SUPPORTS_DAC;
530
531#ifdef _TARGET_X86_
532 return (DWORD)(size_t) dac_cast<TADDR>(pKey);
533#else
534 // <TODO> IA64: Is this a good hashing mechanism on IA64?</TODO>
535 return (DWORD)(((size_t) dac_cast<TADDR>(pKey)) >> 3);
536#endif
537 }
538
539 static KeyPointerType GetKey(EEHashEntry_t *pEntry)
540 {
541 LIMITED_METHOD_CONTRACT;
542
543 return *((KeyPointerType*)pEntry->Key);
544 }
545};
546
547typedef EEHashTable<PTR_VOID, EEPtrHashTableHelper<PTR_VOID>, FALSE> EEPtrHashTable;
548typedef DPTR(EEPtrHashTable) PTR_EEPtrHashTable;
549
550// Define a hash of generic instantiations (represented by a SigTypeContext).
551class EEInstantiationHashTableHelper
552{
553public:
554 static EEHashEntry_t *AllocateEntry(const SigTypeContext *pKey, BOOL bDeepCopy, AllocationHeap pHeap = 0);
555 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap pHeap = 0);
556 static BOOL CompareKeys(EEHashEntry_t *pEntry, const SigTypeContext *pKey);
557 static DWORD Hash(const SigTypeContext *pKey);
558 static const SigTypeContext *GetKey(EEHashEntry_t *pEntry);
559};
560typedef EEHashTable<const SigTypeContext*, EEInstantiationHashTableHelper, FALSE> EEInstantiationHashTable;
561
562// ComComponentInfo hashtable.
563
564struct ClassFactoryInfo
565{
566 GUID m_clsid;
567 WCHAR *m_strServerName;
568};
569
570class EEClassFactoryInfoHashTableHelper
571{
572public:
573 static EEHashEntry_t *AllocateEntry(ClassFactoryInfo *pKey, BOOL bDeepCopy, AllocationHeap Heap);
574 static void DeleteEntry(EEHashEntry_t *pEntry, AllocationHeap Heap);
575 static BOOL CompareKeys(EEHashEntry_t *pEntry, ClassFactoryInfo *pKey);
576 static DWORD Hash(ClassFactoryInfo *pKey);
577 static ClassFactoryInfo *GetKey(EEHashEntry_t *pEntry);
578};
579
580typedef EEHashTable<ClassFactoryInfo *, EEClassFactoryInfoHashTableHelper, TRUE> EEClassFactoryInfoHashTable;
581// Struct to hold a client's iteration state
582struct EEHashTableIteration
583{
584 DWORD m_dwBucket;
585 EEHashEntry_t *m_pEntry;
586
587#ifdef _DEBUG
588 void *m_pTable;
589#endif
590};
591
592#endif /* _EE_HASH_H */
593