1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
5 // File: VirtualCallStub.h
7 // See code:VirtualCallStubManager for details
9 // ============================================================================
11 #ifndef _VIRTUAL_CALL_STUB_H
12 #define _VIRTUAL_CALL_STUB_H
16 #if defined(TARGET_X86)
17 // If this is uncommented, leaves a file "StubLog_<pid>.log" with statistics on the behavior
18 // of stub-based interface dispatch.
19 //#define STUB_LOGGING
24 /////////////////////////////////////////////////////////////////////////////////////
25 // Forward class declarations
30 class VirtualCallStubManager;
31 class VirtualCallStubManagerManager;
33 struct DispatchHolder;
35 struct VTableCallHolder;
37 /////////////////////////////////////////////////////////////////////////////////////
38 // Forward function declarations
39 extern "C" void InContextTPQuickDispatchAsmStub();
41 extern "C" PCODE STDCALL VSD_ResolveWorker(TransitionBlock * pTransitionBlock,
42 TADDR siteAddrForRegisterIndirect,
50 /////////////////////////////////////////////////////////////////////////////////////
51 #if defined(TARGET_X86) || defined(TARGET_AMD64)
55 /////////////////////////////////////////////////////////////////////////////////////
56 // Represents the struct that is added to the resolve cache
57 // NOTE: If you change the layout of this struct, you'll need to update various
58 // ASM helpers in VirtualCallStubCpu that rely on offsets of members.
60 struct ResolveCacheElem
63 size_t token; // DispatchToken
66 // These are used for chaining
67 ResolveCacheElem *pNext;
68 ResolveCacheElem *Next()
69 { LIMITED_METHOD_CONTRACT; return VolatileLoad(&pNext); }
76 BOOL Equals(size_t token, void *pMT)
77 { LIMITED_METHOD_CONTRACT; return (this->pMT == pMT && this->token == token); }
79 BOOL Equals(ResolveCacheElem *pElem)
80 { WRAPPER_NO_CONTRACT; return Equals(pElem->token, pElem->pMT); }
86 e_resolveCacheElem_sizeof_mt = sizeof(void *),
87 e_resolveCacheElem_sizeof_token = sizeof(size_t),
88 e_resolveCacheElem_sizeof_target = sizeof(void *),
89 e_resolveCacheElem_sizeof_next = sizeof(ResolveCacheElem *),
91 e_resolveCacheElem_offset_mt = 0,
92 e_resolveCacheElem_offset_token = e_resolveCacheElem_offset_mt + e_resolveCacheElem_sizeof_mt,
93 e_resolveCacheElem_offset_target = e_resolveCacheElem_offset_token + e_resolveCacheElem_sizeof_token,
94 e_resolveCacheElem_offset_next = e_resolveCacheElem_offset_target + e_resolveCacheElem_sizeof_target,
97 /////////////////////////////////////////////////////////////////////////////////////
98 // A utility class to help manipulate a call site
101 friend class VirtualCallStubManager;
105 // On x86 are four possible kinds of callsites when you take into account all features
106 // Relative: direct call, e.g. "call addr". Not used currently.
107 // RelativeIndirect (JmpRel): indirect call through a relative address, e.g. "call [addr]"
108 // RegisterIndirect: indirect call through a register, e.g. "call [eax]"
109 // DelegateCallSite: anything else, tail called through a register by shuffle thunk, e.g. "jmp [eax]"
111 // On all other platforms we always use an indirect call through an indirection cell
112 // In these cases all calls are made by the platform equivalent of "call [addr]".
114 // DelegateCallSite are particular in that they can come in a variety of forms:
115 // a direct delegate call has a sequence defined by the jit but a multicast or wrapper delegate
116 // are defined in a stub and have a different shape
118 PTR_PCODE m_siteAddr; // Stores the address of an indirection cell
123 #if defined(TARGET_X86)
124 StubCallSite(TADDR siteAddrForRegisterIndirect, PCODE returnAddr);
126 PCODE GetCallerAddress();
127 #else // !defined(TARGET_X86)
128 // On platforms where we always use an indirection cell things
129 // are much simpler - the siteAddr always stores a pointer to a
130 // value that in turn points to the indirection cell.
132 StubCallSite(TADDR siteAddr, PCODE returnAddr)
133 { LIMITED_METHOD_CONTRACT; m_siteAddr = dac_cast<PTR_PCODE>(siteAddr); m_returnAddr = returnAddr; }
135 PCODE GetCallerAddress() { LIMITED_METHOD_CONTRACT; return m_returnAddr; }
136 #endif // !defined(TARGET_X86)
138 PCODE GetSiteTarget() { WRAPPER_NO_CONTRACT; return *(GetIndirectCell()); }
139 void SetSiteTarget(PCODE newTarget);
140 PTR_PCODE GetIndirectCell() { LIMITED_METHOD_CONTRACT; return dac_cast<PTR_PCODE>(m_siteAddr); }
141 PTR_PCODE * GetIndirectCellAddress() { LIMITED_METHOD_CONTRACT; return &m_siteAddr; }
143 PCODE GetReturnAddress() { LIMITED_METHOD_CONTRACT; return m_returnAddr; }
146 // These are the assembly language entry points that the stubs use when they want to go into the EE
148 extern "C" void ResolveWorkerAsmStub(); // resolve a token and transfer control to that method
149 extern "C" void ResolveWorkerChainLookupAsmStub(); // for chaining of entries in the cache
152 extern "C" void BackPatchWorkerAsmStub(); // backpatch a call site to point to a different stub
154 extern "C" void BackPatchWorkerStaticStub(PCODE returnAddr, TADDR siteAddrForRegisterIndirect);
155 #endif // TARGET_UNIX
159 typedef VPTR(class VirtualCallStubManager) PTR_VirtualCallStubManager;
161 // VirtualCallStubManager is the heart of the stub dispatch logic. See the book of the runtime entry
163 // file:../../doc/BookOfTheRuntime/ClassLoader/VirtualStubDispatchDesign.doc
165 // The basic idea is that a call to an interface (it could also be used for virtual calls in general, but we
166 // do not do this), is simply the code
168 // call [DispatchCell]
170 // Where we make sure 'DispatchCell' points at stubs that will do the right thing. DispatchCell is writable
171 // so we can update the code over time. There are three basic types of stubs that the dispatch cell can point
173 // * Lookup: The initial stub that has no 'fast path' and simply pushes a ID for interface being called
174 // and calls into the runtime at code:VirtualCallStubManager.ResolveWorkerStatic.
175 // * Dispatch: Lookup stubs are patched to this stub which has a fast path that checks for a particular
176 // Method Table and if that fails jumps to code that
177 // * Decrements a 'missCount' (starts out as code:STUB_MISS_COUNT_VALUE). If this count goes to zero
178 // code:VirtualCallStubManager.BackPatchWorkerStatic is called, morphs it into a resolve stub
179 // (however since this decrementing logic is SHARED among all dispatch stubs, it may take
180 // multiples of code:STUB_MISS_COUNT_VALUE if multiple call sites are actively polymorphic (this
182 // * Calls a resolve stub (Whenever a dispatch stub is created, it always has a corresponding resolve
183 // stub (but the resolve stubs are shared among many dispatch stubs).
184 // * Resolve: see code:ResolveStub. This looks up the Method table in a process wide cache (see
185 // code:ResolveCacheElem, and if found, jumps to it. This code path is about 17 instructions long (so
186 // pretty fast, but certainly much slower than a normal call). If the method table is not found in
187 // the cache, it calls into the runtime code:VirtualCallStubManager.ResolveWorkerStatic, which
189 // So the general progression is call site's cells
190 // * start out life pointing to a lookup stub
191 // * On first call they get updated into a dispatch stub. When this misses, it calls a resolve stub,
192 // which populates a resovle stub's cache, but does not update the call site' cell (thus it is still
193 // pointing at the dispatch cell.
194 // * After code:STUB_MISS_COUNT_VALUE misses, we update the call site's cell to point directly at the
195 // resolve stub (thus avoiding the overhead of the quick check that always seems to be failing and
196 // the miss count update).
198 // QUESTION: What is the lifetimes of the various stubs and hash table entries?
200 // QUESTION: There does not seem to be any logic that will change a call site's cell once it becomes a
201 // Resolve stub. Thus once a particular call site becomes a Resolve stub we live with the Resolve stub's
202 // (in)efficiency forever.
204 // see code:#StubDispatchNotes for more
205 class VirtualCallStubManager : public StubManager
207 friend class VirtualCallStubManagerManager;
208 friend class VirtualCallStubManagerIterator;
210 #if defined(DACCESS_COMPILE)
211 friend class ClrDataAccess;
212 friend class DacDbiInterfaceImpl;
213 #endif // DACCESS_COMPILE
215 VPTR_VTABLE_CLASS(VirtualCallStubManager, StubManager)
219 virtual const char * DbgGetName() { LIMITED_METHOD_CONTRACT; return "VirtualCallStubManager"; }
222 // The reason for our existence, return a callstub for type id and slot number
223 // where type id = 0 for the class contract (i.e. a virtual call), and type id > 0 for an
224 // interface invoke where the id indicates which interface it is.
226 // The function is idempotent, i.e.
227 // you'll get the same callstub twice if you call it with identical inputs.
228 PCODE GetCallStub(TypeHandle ownerType, MethodDesc *pMD);
229 PCODE GetCallStub(TypeHandle ownerType, DWORD slot);
231 // Stubs for vtable-based virtual calls with no lookups
232 PCODE GetVTableCallStub(DWORD slot);
234 // Generate an fresh indirection cell.
235 BYTE* GenerateStubIndirection(PCODE stub, BOOL fUseRecycledCell = FALSE);
237 // Set up static data structures - called during EEStartup
238 static void InitStatic();
239 static void UninitStatic();
241 // Per instance initialization - called during AppDomain::Init and ::Uninit and for collectible loader allocators
242 void Init(BaseDomain* pDomain, LoaderAllocator *pLoaderAllocator);
245 //@TODO: the logging should be tied into the VMs normal loggin mechanisms,
246 //@TODO: for now we just always write a short log file called "StubLog_<pid>.log"
247 static void StartupLogging();
248 static void LoggingDump();
249 static void FinishLogging();
251 static void ResetCache();
253 // Reclaim/rearrange any structures that can only be done during a gc sync point.
254 // This is the mechanism we are using to avoid synchronization of alot of our
255 // cache and hash table accesses. We are requiring that during a gc sync point we are not
256 // executing any stub code at all, hence at this time we are serialized on a single thread (gc)
257 // and no other thread is accessing the data structures.
258 static void ReclaimAll();
261 #ifndef DACCESS_COMPILE
262 VirtualCallStubManager()
264 cache_entry_rangeList(),
266 m_loaderAllocator(NULL),
267 m_initialReservedMemForHeaps(NULL),
268 m_FreeIndCellList(NULL),
269 m_RecycledIndCellList(NULL),
271 cache_entry_heap(NULL),
276 m_fShouldAllocateLongJumpDispatchStubs(FALSE),
283 m_cur_counter_block(NULL),
284 m_cur_counter_block_for_reclaim(NULL),
285 m_cur_counter_block_for_reclaim_index(NULL),
288 LIMITED_METHOD_CONTRACT;
289 ZeroMemory(&stats, sizeof(stats));
292 ~VirtualCallStubManager();
293 #endif // !DACCESS_COMPILE
295 static BOOL isStubStatic(PCODE addr)
298 StubCodeBlockKind sk = RangeSectionStubManager::GetStubKind(addr);
300 return sk == STUB_CODE_BLOCK_VSD_DISPATCH_STUB ||
301 sk == STUB_CODE_BLOCK_VSD_LOOKUP_STUB ||
302 sk == STUB_CODE_BLOCK_VSD_RESOLVE_STUB ||
303 sk == STUB_CODE_BLOCK_VSD_VTABLE_STUB;
306 static BOOL isDispatchingStubStatic(PCODE addr)
309 StubCodeBlockKind sk = RangeSectionStubManager::GetStubKind(addr);
311 return sk == STUB_CODE_BLOCK_VSD_DISPATCH_STUB;
314 static BOOL isResolvingStubStatic(PCODE addr)
317 StubCodeBlockKind sk = RangeSectionStubManager::GetStubKind(addr);
319 return sk == STUB_CODE_BLOCK_VSD_RESOLVE_STUB;
322 static BOOL isLookupStubStatic(PCODE addr)
325 StubCodeBlockKind sk = RangeSectionStubManager::GetStubKind(addr);
327 return sk == STUB_CODE_BLOCK_VSD_LOOKUP_STUB;
330 static BOOL isVtableCallStubStatic(PCODE addr)
333 StubCodeBlockKind sk = RangeSectionStubManager::GetStubKind(addr);
335 return sk == STUB_CODE_BLOCK_VSD_VTABLE_STUB;
338 //use range lists to track the chunks of memory that are part of each heap
339 LockedRangeList cache_entry_rangeList;
341 // Get dac-ized pointers to rangelist.
342 RangeList* GetCacheEntryRangeList()
345 TADDR addr = PTR_HOST_MEMBER_TADDR(VirtualCallStubManager, this, cache_entry_rangeList);
346 return PTR_RangeList(addr);
351 //allocate and initialize a stub of the desired kind
352 DispatchHolder *GenerateDispatchStub(PCODE addrOfCode,
355 size_t dispatchToken,
356 bool *pMayHaveReenteredCooperativeGCMode);
359 // Used to allocate a long jump dispatch stub. See comment around
360 // m_fShouldAllocateLongJumpDispatchStubs for explanation.
361 DispatchHolder *GenerateDispatchStubLong(PCODE addrOfCode,
364 size_t dispatchToken,
365 bool *pMayHaveReenteredCooperativeGCMode);
368 ResolveHolder *GenerateResolveStub(PCODE addrOfResolver,
371 #if defined(TARGET_X86) && !defined(UNIX_X86_ABI)
372 , size_t stackArgumentsSize
376 LookupHolder *GenerateLookupStub(PCODE addrOfResolver,
377 size_t dispatchToken);
379 VTableCallHolder* GenerateVTableCallStub(DWORD slot);
381 // The resolve cache is static across all AppDomains
382 ResolveCacheElem *GenerateResolveCacheElem(void *addrOfCode,
385 bool *pMayHaveReenteredCooperativeGCMode);
387 ResolveCacheElem *GetResolveCacheElem(void *pMT,
391 //Given a dispatch token, an object and a method table, determine the
392 //target address to go to. The return value (BOOL) states whether this address
393 //is cacheable or not.
394 static BOOL Resolver(MethodTable * pMT,
396 OBJECTREF * protectedObj,
398 BOOL throwOnConflict);
400 // This can be used to find a target without needing the ability to throw
401 static BOOL TraceResolver(Object *pObj, DispatchToken token, TraceDestination *trace);
404 // Return the MethodDesc corresponding to this token.
405 static MethodDesc *GetRepresentativeMethodDescFromToken(DispatchToken token, MethodTable *pMT);
406 static MethodDesc *GetInterfaceMethodDescFromToken(DispatchToken token);
407 static MethodTable *GetTypeFromToken(DispatchToken token);
409 //This is used to get the token out of a stub
410 static size_t GetTokenFromStub(PCODE stub);
412 //This is used to get the token out of a stub and we know the stub manager and stub kind
413 static size_t GetTokenFromStubQuick(VirtualCallStubManager * pMgr, PCODE stub, StubCodeBlockKind kind);
415 // General utility functions
416 // Quick lookup in the cache. NOTHROW, GC_NOTRIGGER
417 static PCODE CacheLookup(size_t token, UINT16 tokenHash, MethodTable *pMT);
419 // Full exhaustive lookup. THROWS, GC_TRIGGERS
420 static PCODE GetTarget(DispatchToken token, MethodTable *pMT, BOOL throwOnConflict);
423 // Given a dispatch token, return true if the token represents an interface, false if just a slot.
424 static BOOL IsInterfaceToken(DispatchToken token);
426 // Given a dispatch token, return true if the token represents a slot on the target.
427 static BOOL IsClassToken(DispatchToken token);
430 static ResolveCacheElem* __fastcall PromoteChainEntry(ResolveCacheElem *pElem);
433 // Flags used by the non-x86 versions of VSD_ResolveWorker
435 #define SDF_ResolveBackPatch (0x01)
436 #define SDF_ResolvePromoteChain (0x02)
437 #define SDF_ResolveFlags (0x03)
439 // These method needs to call the instance methods.
440 friend PCODE VSD_ResolveWorker(TransitionBlock * pTransitionBlock,
441 TADDR siteAddrForRegisterIndirect,
448 #if defined(TARGET_X86) && defined(TARGET_UNIX)
449 friend void BackPatchWorkerStaticStub(PCODE returnAddr, TADDR siteAddrForRegisterIndirect);
452 //These are the entrypoints that the stubs actually end up calling via the
453 // xxxAsmStub methods above
454 static void STDCALL BackPatchWorkerStatic(PCODE returnAddr, TADDR siteAddrForRegisterIndirect);
457 PCODE ResolveWorker(StubCallSite* pCallSite, OBJECTREF *protectedObj, DispatchToken token, StubCodeBlockKind stubKind);
458 void BackPatchWorker(StubCallSite* pCallSite);
460 //Change the callsite to point to stub
461 void BackPatchSite(StubCallSite* pCallSite, PCODE stub);
464 /* the following two public functions are to support tracing or stepping thru
465 stubs via the debugger. */
466 virtual BOOL CheckIsStub_Internal(PCODE stubStartAddress);
467 virtual BOOL TraceManager(Thread *thread,
468 TraceDestination *trace,
473 LIMITED_METHOD_CONTRACT;
476 retval+=indcell_heap->GetSize();
478 retval+=cache_entry_heap->GetSize();
483 /* the following two private functions are to support tracing or stepping thru
484 stubs via the debugger. */
485 virtual BOOL DoTraceStub(PCODE stubStartAddress,
486 TraceDestination *trace);
489 // The parent domain of this manager
490 PTR_BaseDomain parentDomain;
492 PTR_LoaderAllocator m_loaderAllocator;
494 BYTE * m_initialReservedMemForHeaps;
496 static const UINT32 INDCELLS_PER_BLOCK = 32; // 32 indirection cells per block.
498 CrstExplicitInit m_indCellLock;
500 // List of free indirection cells. The cells were directly allocated from the loader heap
501 // (code:VirtualCallStubManager::GenerateStubIndirection)
502 BYTE * m_FreeIndCellList;
504 // List of recycled indirection cells. The cells were recycled from finalized dynamic methods
505 // (code:LCGMethodResolver::RecycleIndCells).
506 BYTE * m_RecycledIndCellList;
508 #ifndef DACCESS_COMPILE
509 // This methods returns the a free cell from m_FreeIndCellList. It returns NULL if the list is empty.
510 BYTE * GetOneFreeIndCell()
514 return GetOneIndCell(&m_FreeIndCellList);
517 // This methods returns the a recycled cell from m_RecycledIndCellList. It returns NULL if the list is empty.
518 BYTE * GetOneRecycledIndCell()
522 return GetOneIndCell(&m_RecycledIndCellList);
525 // This methods returns the a cell from ppList. It returns NULL if the list is empty.
526 BYTE * GetOneIndCell(BYTE ** ppList)
532 PRECONDITION(CheckPointer(ppList));
533 PRECONDITION(m_indCellLock.OwnedByCurrentThread());
536 BYTE * temp = *ppList;
540 BYTE * pNext = *((BYTE **)temp);
548 // insert a linked list of indirection cells at the beginning of m_FreeIndCellList
549 void InsertIntoFreeIndCellList(BYTE * head, BYTE * tail)
553 InsertIntoIndCellList(&m_FreeIndCellList, head, tail);
556 // insert a linked list of indirection cells at the beginning of ppList
557 void InsertIntoIndCellList(BYTE ** ppList, BYTE * head, BYTE * tail)
562 PRECONDITION(CheckPointer(ppList));
563 PRECONDITION(CheckPointer(head));
564 PRECONDITION(CheckPointer(tail));
565 PRECONDITION(m_indCellLock.OwnedByCurrentThread());
568 BYTE * temphead = *ppList;
569 *((BYTE**)tail) = temphead;
572 #endif // !DACCESS_COMPILE
574 PTR_LoaderHeap indcell_heap; // indirection cells go here
575 PTR_LoaderHeap cache_entry_heap; // resolve cache elem entries go here
576 PTR_CodeFragmentHeap lookup_heap; // lookup stubs go here
577 PTR_CodeFragmentHeap dispatch_heap; // dispatch stubs go here
578 PTR_CodeFragmentHeap resolve_heap; // resolve stubs go here
579 PTR_CodeFragmentHeap vtable_heap; // vtable-based jump stubs go here
582 // When we layout the stub heaps, we put them close together in a sequential order
583 // so that we maximize performance with respect to branch predictions. On AMD64,
584 // dispatch stubs use a rel32 jump on failure to the resolve stub. This works for
585 // a while because of the ordering, but as soon as we have to start allocating more
586 // memory for either the dispatch or resolve heaps we have a chance that we'll be
587 // further away than a rel32 jump can reach, because we're in a 64-bit address
588 // space. As such, this flag will indicate when we allocate the first dispatch stub
589 // that cannot reach a resolve stub, and when this happens we'll switch over to
590 // allocating the larger version of the dispatch stub which contains an abs64 jump.
591 //@TODO: This is a bit of a workaround, but the limitations of LoaderHeap require that we
592 //@TODO: take this approach. Hopefully in Orcas we'll have a chance to rewrite LoaderHeap.
593 BOOL m_fShouldAllocateLongJumpDispatchStubs; // Defaults to FALSE.
596 BucketTable * lookups; // hash table of lookups keyed by tokens
597 BucketTable * cache_entries; // hash table of dispatch token/target structs for dispatch cache
598 BucketTable * dispatchers; // hash table of dispatching stubs keyed by tokens/actualtype
599 BucketTable * resolvers; // hash table of resolvers keyed by tokens/resolverstub
600 BucketTable * vtableCallers; // hash table of vtable call stubs keyed by slot values
602 // This structure is used to keep track of the fail counters.
603 // We only need one fail counter per ResolveStub,
604 // and most programs use less than 250 ResolveStubs
605 // We allocate these on the main heap using "new counter block"
608 static const UINT32 MAX_COUNTER_ENTRIES = 256-2; // 254 counters should be enough for most cases.
610 counter_block * next; // the next block
611 UINT32 used; // the index of the next free entry
612 INT32 block[MAX_COUNTER_ENTRIES]; // the counters
615 counter_block *m_counters; // linked list of counter blocks of failure counters
616 counter_block *m_cur_counter_block; // current block for updating counts
617 counter_block *m_cur_counter_block_for_reclaim; // current block for updating
618 UINT32 m_cur_counter_block_for_reclaim_index; // index into the current block for updating
620 // Used to keep track of all the VCSManager objects in the system.
621 PTR_VirtualCallStubManager m_pNext; // Linked list pointer
624 // Given a stub address, find the VCSManager that owns it.
625 static VirtualCallStubManager *FindStubManager(PCODE addr,
626 StubCodeBlockKind* wbStubKind = NULL);
628 #ifndef DACCESS_COMPILE
629 // insert a linked list of indirection cells at the beginning of m_RecycledIndCellList
630 void InsertIntoRecycledIndCellList_Locked(BYTE * head, BYTE * tail)
638 CrstHolder lh(&m_indCellLock);
640 InsertIntoIndCellList(&m_RecycledIndCellList, head, tail);
642 #endif // !DACCESS_COMPILE
644 // These are the counters for keeping statistics
647 UINT32 site_counter; //# of call sites
648 UINT32 stub_lookup_counter; //# of lookup stubs
649 UINT32 stub_poly_counter; //# of resolve stubs
650 UINT32 stub_mono_counter; //# of dispatch stubs
651 UINT32 stub_vtable_counter; //# of vtable call stubs
652 UINT32 site_write; //# of call site backpatch writes
653 UINT32 site_write_poly; //# of call site backpatch writes to point to resolve stubs
654 UINT32 site_write_mono; //# of call site backpatch writes to point to dispatch stubs
655 UINT32 worker_call; //# of calls into ResolveWorker
656 UINT32 worker_call_no_patch; //# of times call_worker resulted in no patch
657 UINT32 worker_collide_to_mono; //# of times we converted a poly stub to a mono stub instead of writing the cache entry
658 UINT32 stub_space; //# of bytes of stubs
659 UINT32 cache_entry_counter; //# of cache structs
660 UINT32 cache_entry_space; //# of bytes used by cache lookup structs
665 #ifdef DACCESS_COMPILE
667 virtual void DoEnumMemoryRegions(CLRDataEnumMemoryFlags flags);
668 virtual LPCWSTR GetStubManagerName(PCODE addr)
671 CONSISTENCY_CHECK(isStub(addr));
673 return W("Unexpected. RangeSectionStubManager should report the name");
678 /********************************************************************************************************
679 ********************************************************************************************************/
680 typedef VPTR(class VirtualCallStubManagerManager) PTR_VirtualCallStubManagerManager;
682 class VirtualCallStubManagerIterator;
683 class VirtualCallStubManagerManager : public StubManager
685 VPTR_VTABLE_CLASS(VirtualCallStubManagerManager, StubManager)
687 friend class StubManager;
688 friend class VirtualCallStubManager;
689 friend class VirtualCallStubManagerIterator;
690 friend class StubManagerIterator;
693 virtual BOOL TraceManager(Thread *thread, TraceDestination *trace,
694 T_CONTEXT *pContext, BYTE **pRetAddr);
696 virtual BOOL CheckIsStub_Internal(PCODE stubStartAddress);
698 virtual BOOL DoTraceStub(PCODE stubStartAddress, TraceDestination *trace);
700 static MethodDesc *Entry2MethodDesc(PCODE stubStartAddress, MethodTable *pMT);
702 #ifdef DACCESS_COMPILE
703 virtual void DoEnumMemoryRegions(CLRDataEnumMemoryFlags flags);
704 virtual LPCWSTR GetStubManagerName(PCODE addr)
705 { WRAPPER_NO_CONTRACT; return FindVirtualCallStubManager(addr)->GetStubManagerName(addr); }
709 // Used to keep track of all the VCSManager objects in the system.
710 PTR_VirtualCallStubManager m_pManagers; // Head of the linked list
712 #ifndef DACCESS_COMPILE
713 // Ctor. This is only used by StaticInit.
714 VirtualCallStubManagerManager();
717 // A cache element to quickly check the last matched manager.
718 Volatile<VirtualCallStubManager*> m_pCacheElem;
720 // RW lock for reading entries and removing them.
721 SimpleRWLock m_RWLock;
723 // This will look through all the managers in an intelligent fashion to
724 // find the manager that owns the address.
725 VirtualCallStubManager *FindVirtualCallStubManager(PCODE stubAddress);
728 // Add a VCSManager to the linked list.
729 void AddStubManager(VirtualCallStubManager *pMgr);
731 // Remove a VCSManager from the linked list.
732 void RemoveStubManager(VirtualCallStubManager *pMgr);
734 VirtualCallStubManager *FirstManager()
735 { WRAPPER_NO_CONTRACT; return m_pManagers; }
737 #ifndef DACCESS_COMPILE
738 static void InitStatic();
742 SPTR_DECL(VirtualCallStubManagerManager, g_pManager);
744 static VirtualCallStubManagerManager *GlobalManager()
745 { LIMITED_METHOD_DAC_CONTRACT; CONSISTENCY_CHECK(CheckPointer(g_pManager)); return g_pManager; }
747 VirtualCallStubManagerIterator IterateVirtualCallStubManagers();
750 // Debug helper to help identify stub-managers.
751 virtual const char * DbgGetName() { LIMITED_METHOD_CONTRACT; return "VirtualCallStubManagerManager"; }
755 /********************************************************************************************************
756 ********************************************************************************************************/
757 class VirtualCallStubManagerIterator
759 friend class VirtualCallStubManagerManager;
763 VirtualCallStubManager *Current();
766 inline VirtualCallStubManagerIterator(const VirtualCallStubManagerIterator &it);
769 inline VirtualCallStubManagerIterator(VirtualCallStubManagerManager *pMgr);
772 VirtualCallStubManager *m_pCurMgr;
775 /////////////////////////////////////////////////////////////////////////////////////////////
777 inline VirtualCallStubManagerIterator::VirtualCallStubManagerIterator(VirtualCallStubManagerManager *pMgr)
778 : m_fIsStart(TRUE), m_pCurMgr(pMgr->m_pManagers)
780 LIMITED_METHOD_DAC_CONTRACT;
781 CONSISTENCY_CHECK(CheckPointer(pMgr));
784 /////////////////////////////////////////////////////////////////////////////////////////////
786 inline VirtualCallStubManagerIterator::VirtualCallStubManagerIterator(const VirtualCallStubManagerIterator &it)
787 : m_fIsStart(it.m_fIsStart), m_pCurMgr(it.m_pCurMgr)
789 LIMITED_METHOD_DAC_CONTRACT;
792 /********************************************************************************************************
795 A note on approach. The cache and hash tables used by the stub and lookup mechanism
796 are designed with an eye to minimizing interlocking and/or syncing and/or locking operations.
797 They are intended to run in a highly concurrent environment. Since there is no magic,
798 some tradeoffs and and some implementation constraints are required. The basic notion
799 is that if all reads and writes are atomic and if all functions and operations operate
800 correctly in the face of commutative reorderings of the visibility of all reads and writes
801 across threads, then we don't have to interlock, sync, or serialize. Our approximation of
804 1. All reads and all writes to tables must be atomic. This effectively limits the actual entry
805 size in a table to be a pointer or a pointer sized thing.
807 2. All functions, like comparisons for equality or computation of hash values must function
808 correctly in the face of concurrent updating of the underlying table. This is accomplished
809 by making the underlying structures/entries effectively immutable, if concurrency is in anyway possible.
810 By effectively immutatable, we mean that the stub or token structure is either immutable or that
811 if it is ever written, all possible concurrent writes are attempting to write the same value (atomically)
812 or that the competing (atomic) values do not affect correctness, and that the function operates correctly whether
813 or not any of the writes have taken place (is visible yet). The constraint we maintain is that all competeing
814 updates (and their visibility or lack thereof) do not alter the correctness of the program.
816 3. All tables are inexact. The counts they hold (e.g. number of contained entries) may be inaccurate,
817 but that inaccurracy cannot affect their correctness. Table modifications, such as insertion of
818 an new entry may not succeed, but such failures cannot affect correctness. This implies that just
819 because a stub/entry is not present in a table, e.g. has been removed, that does not mean that
820 it is not in use. It also implies that internal table structures, such as discarded hash table buckets,
821 cannot be freely recycled since another concurrent thread may still be walking thru it.
823 4. Occasionally it is necessary to pick up the pieces that have been dropped on the floor
824 so to speak, e.g. actually recycle hash buckets that aren't in use. Since we have a natural
825 sync point already in the GC, we use that to provide cleanup points. We need to make sure that code that
826 is walking our structures is not a GC safe point. Hence if the GC calls back into us inside the GC
827 sync point, we know that nobody is inside our structures and we can safely rearrange and recycle things.
828 ********************************************************************************************************/
830 //initial and increment value for fail stub counters
832 extern UINT32 STUB_MISS_COUNT_VALUE;
833 extern UINT32 STUB_COLLIDE_WRITE_PCT;
834 extern UINT32 STUB_COLLIDE_MONO_PCT;
835 #else // !STUB_LOGGING
836 #define STUB_MISS_COUNT_VALUE 100
837 #define STUB_COLLIDE_WRITE_PCT 100
838 #define STUB_COLLIDE_MONO_PCT 0
839 #endif // !STUB_LOGGING
841 //size and mask of the cache used by resolve stubs
842 // CALL_STUB_CACHE_SIZE must be equal to 2^CALL_STUB_CACHE_NUM_BITS
843 #define CALL_STUB_CACHE_NUM_BITS 12 //10
844 #define CALL_STUB_CACHE_SIZE 4096 //1024
845 #define CALL_STUB_CACHE_MASK (CALL_STUB_CACHE_SIZE-1)
846 #define CALL_STUB_CACHE_PROBES 5
847 //min sizes for BucketTable and buckets and the growth and hashing constants
848 #define CALL_STUB_MIN_BUCKETS 32
849 #define CALL_STUB_MIN_ENTRIES 4
850 //this is so that the very first growth will jump from 4 to 32 entries, then double from there.
851 #define CALL_STUB_SECONDARY_ENTRIES 8
852 #define CALL_STUB_GROWTH_FACTOR 2
853 #define CALL_STUB_LOAD_FACTOR 90
854 #define CALL_STUB_HASH_CONST1 1327
855 #define CALL_STUB_HASH_CONST2 43627
856 #define LARGE_PRIME 7199369
857 //internal layout of buckets=size-1,count,entries....
858 #define CALL_STUB_MASK_INDEX 0
859 #define CALL_STUB_COUNT_INDEX 1
860 #define CALL_STUB_DEAD_LINK 2
861 #define CALL_STUB_FIRST_INDEX 3
862 //marker entries in cache and hash tables
863 #define CALL_STUB_EMPTY_ENTRY 0
864 // number of successes for a chained element before it gets moved to the front
865 #define CALL_STUB_CACHE_INITIAL_SUCCESS_COUNT (0x100)
867 /*******************************************************************************************************
868 Entry is an abstract class. We will make specific subclasses for each kind of
869 entry. Entries hold references to stubs or tokens. The principle thing they provide
870 is a virtual Equals function that is used by the caching and hashing tables within which
871 the stubs and tokens are stored. Entries are typically stack allocated by the routines
872 that call into the hash and caching functions, and the functions stuff stubs into the entry
873 to do the comparisons. Essentially specific entry subclasses supply a vtable to a stub
874 as and when needed. This means we don't have to have vtables attached to stubs.
876 Summarizing so far, there is a struct for each kind of stub or token of the form XXXXStub.
877 They provide that actual storage layouts.
878 There is a struct in which each stub which has code is contained of the form XXXXHolder.
879 They provide alignment and anciliary storage for the stub code.
880 There is a subclass of Entry for each kind of stub or token, of the form XXXXEntry.
881 They provide the specific implementations of the virtual functions declared in Entry. */
885 //access and compare the keys of the entry
886 virtual BOOL Equals(size_t keyA, size_t keyB)=0;
887 virtual size_t KeyA()=0;
888 virtual size_t KeyB()=0;
890 //contents is the struct or token that the entry exposes
891 virtual void SetContents(size_t contents)=0;
894 /* define the platform specific Stubs and stub holders */
896 #include <virtualcallstubcpu.hpp>
898 #if USES_LOOKUP_STUBS
899 /**********************************************************************************************
900 LookupEntry wraps LookupStubs and provide the concrete implementation of the abstract class Entry.
901 Virtual and interface call sites when they are first jitted point to LookupStubs. The hash table
902 that contains look up stubs is keyed by token, hence the Equals function uses the embedded token in
903 the stub for comparison purposes. Since we are willing to allow duplicates in the hash table (as
904 long as they are relatively rare) we do use direct comparison of the tokens rather than extracting
905 the fields from within the tokens, for perf reasons. */
906 class LookupEntry : public Entry
909 //Creates an entry that wraps lookup stub s
910 LookupEntry(size_t s)
912 LIMITED_METHOD_CONTRACT;
913 _ASSERTE(VirtualCallStubManager::isLookupStubStatic((PCODE)s));
914 stub = (LookupStub*) s;
917 //default constructor to allow stack and inline allocation of lookup entries
918 LookupEntry() {LIMITED_METHOD_CONTRACT; stub = NULL;}
920 //implementations of abstract class Entry
921 BOOL Equals(size_t keyA, size_t keyB)
922 { WRAPPER_NO_CONTRACT; return stub && (keyA == KeyA()) && (keyB == KeyB()); }
924 size_t KeyA() { WRAPPER_NO_CONTRACT; return Token(); }
925 size_t KeyB() { WRAPPER_NO_CONTRACT; return (size_t)0; }
927 void SetContents(size_t contents)
929 LIMITED_METHOD_CONTRACT;
930 _ASSERTE(VirtualCallStubManager::isLookupStubStatic((PCODE)contents));
931 stub = LookupHolder::FromLookupEntry((PCODE)contents)->stub();
934 //extract the token of the underlying lookup stub
936 inline size_t Token() { LIMITED_METHOD_CONTRACT; return stub ? stub->token() : 0; }
939 LookupStub* stub; //the stub the entry wrapping
941 #endif // USES_LOOKUP_STUBS
943 class VTableCallEntry : public Entry
946 //Creates an entry that wraps vtable call stub
947 VTableCallEntry(size_t s)
949 LIMITED_METHOD_CONTRACT;
950 _ASSERTE(VirtualCallStubManager::isVtableCallStubStatic((PCODE)s));
951 stub = (VTableCallStub*)s;
954 //default constructor to allow stack and inline allocation of vtable call entries
955 VTableCallEntry() { LIMITED_METHOD_CONTRACT; stub = NULL; }
957 //implementations of abstract class Entry
958 BOOL Equals(size_t keyA, size_t keyB)
960 WRAPPER_NO_CONTRACT; return stub && (keyA == KeyA()) && (keyB == KeyB());
963 size_t KeyA() { WRAPPER_NO_CONTRACT; return Token(); }
964 size_t KeyB() { WRAPPER_NO_CONTRACT; return (size_t)0; }
966 void SetContents(size_t contents)
968 LIMITED_METHOD_CONTRACT;
969 _ASSERTE(VirtualCallStubManager::isVtableCallStubStatic((PCODE)contents));
970 stub = VTableCallHolder::FromVTableCallEntry((PCODE)contents)->stub();
973 //extract the token of the underlying lookup stub
975 inline size_t Token() { LIMITED_METHOD_CONTRACT; return stub ? stub->token() : 0; }
978 VTableCallStub* stub; //the stub the entry wrapping
981 /**********************************************************************************************
982 ResolveCacheEntry wraps a ResolveCacheElem and provides lookup functionality for entries that
983 were created that may be added to the ResolveCache
985 class ResolveCacheEntry : public Entry
988 ResolveCacheEntry(size_t elem)
990 LIMITED_METHOD_CONTRACT;
992 pElem = (ResolveCacheElem*) elem;
995 //default constructor to allow stack and inline allocation of lookup entries
996 ResolveCacheEntry() { LIMITED_METHOD_CONTRACT; pElem = NULL; }
998 //access and compare the keys of the entry
999 virtual BOOL Equals(size_t keyA, size_t keyB)
1000 { WRAPPER_NO_CONTRACT; return pElem && (keyA == KeyA()) && (keyB == KeyB()); }
1001 virtual size_t KeyA()
1002 { LIMITED_METHOD_CONTRACT; return pElem != NULL ? pElem->token : 0; }
1003 virtual size_t KeyB()
1004 { LIMITED_METHOD_CONTRACT; return pElem != NULL ? (size_t) pElem->pMT : 0; }
1006 //contents is the struct or token that the entry exposes
1007 virtual void SetContents(size_t contents)
1009 LIMITED_METHOD_CONTRACT;
1010 pElem = (ResolveCacheElem*) contents;
1013 inline const BYTE *Target()
1015 LIMITED_METHOD_CONTRACT;
1016 return pElem != NULL ? (const BYTE *)pElem->target : NULL;
1020 ResolveCacheElem *pElem;
1023 /**********************************************************************************************
1024 ResolveEntry wraps ResolveStubs and provide the concrete implementation of the abstract class Entry.
1025 Polymorphic call sites and monomorphic calls that fail end up in a ResolveStub. Resolve stubs
1026 are stored in hash tables keyed by token, hence the Equals function uses the embedded token in
1027 the stub for comparison purposes. Since we are willing to allow duplicates in the hash table (as
1028 long as they are relatively rare) we do use direct comparison of the tokens rather than extracting
1029 the fields from within the tokens, for perf reasons. */
1030 class ResolveEntry : public Entry
1033 //Creates an entry that wraps resolve stub s
1034 ResolveEntry (size_t s)
1036 LIMITED_METHOD_CONTRACT;
1037 _ASSERTE(VirtualCallStubManager::isResolvingStubStatic((PCODE)s));
1038 stub = (ResolveStub*) s;
1040 //default constructor to allow stack and inline allocation of resovler entries
1041 ResolveEntry() { LIMITED_METHOD_CONTRACT; stub = CALL_STUB_EMPTY_ENTRY; }
1043 //implementations of abstract class Entry
1044 inline BOOL Equals(size_t keyA, size_t keyB)
1045 { WRAPPER_NO_CONTRACT; return stub && (keyA == KeyA()) && (keyB == KeyB()); }
1046 inline size_t KeyA() { WRAPPER_NO_CONTRACT; return Token(); }
1047 inline size_t KeyB() { WRAPPER_NO_CONTRACT; return (size_t)0; }
1049 void SetContents(size_t contents)
1051 LIMITED_METHOD_CONTRACT;
1052 _ASSERTE(VirtualCallStubManager::isResolvingStubStatic((PCODE)contents));
1053 stub = ResolveHolder::FromResolveEntry((PCODE)contents)->stub();
1055 //extract the token of the underlying resolve stub
1056 inline size_t Token() { WRAPPER_NO_CONTRACT; return stub ? (size_t)(stub->token()) : 0; }
1058 ResolveStub* stub; //the stub the entry is wrapping
1061 /**********************************************************************************************
1062 DispatchEntry wraps DispatchStubs and provide the concrete implementation of the abstract class Entry.
1063 Monomorphic and mostly monomorphic call sites eventually point to DispatchStubs. Dispatch stubs
1064 are placed in hash and cache tables keyed by the expected Method Table and token they are built for.
1065 Since we are willing to allow duplicates in the hash table (as long as they are relatively rare)
1066 we do use direct comparison of the tokens rather than extracting the fields from within the tokens,
1068 class DispatchEntry : public Entry
1071 //Creates an entry that wraps dispatch stub s
1072 DispatchEntry (size_t s)
1074 LIMITED_METHOD_CONTRACT;
1075 _ASSERTE(VirtualCallStubManager::isDispatchingStubStatic((PCODE)s));
1076 stub = (DispatchStub*) s;
1078 //default constructor to allow stack and inline allocation of resovler entries
1079 DispatchEntry() { LIMITED_METHOD_CONTRACT; stub = CALL_STUB_EMPTY_ENTRY; }
1081 //implementations of abstract class Entry
1082 inline BOOL Equals(size_t keyA, size_t keyB)
1083 { WRAPPER_NO_CONTRACT; return stub && (keyA == KeyA()) && (keyB == KeyB()); }
1084 inline size_t KeyA() { WRAPPER_NO_CONTRACT; return Token(); }
1085 inline size_t KeyB() { WRAPPER_NO_CONTRACT; return ExpectedMT();}
1087 void SetContents(size_t contents)
1089 LIMITED_METHOD_CONTRACT;
1090 _ASSERTE(VirtualCallStubManager::isDispatchingStubStatic((PCODE)contents));
1091 stub = DispatchHolder::FromDispatchEntry((PCODE)contents)->stub();
1094 //extract the fields of the underlying dispatch stub
1095 inline size_t ExpectedMT()
1096 { WRAPPER_NO_CONTRACT; return stub ? (size_t)(stub->expectedMT()) : 0; }
1100 WRAPPER_NO_CONTRACT;
1103 ResolveHolder * resolveHolder = ResolveHolder::FromFailEntry(stub->failTarget());
1104 size_t token = resolveHolder->stub()->token();
1105 _ASSERTE(token == VirtualCallStubManager::GetTokenFromStub((PCODE)stub));
1114 inline PCODE Target()
1115 { WRAPPER_NO_CONTRACT; return stub ? stub->implTarget() : 0; }
1121 /*************************************************************************************************
1122 DispatchCache is the cache table that the resolve stubs use for inline polymorphic resolution
1123 of a call. The cache entry is logically a triplet of (method table, token, impl address) where method table
1124 is the type of the calling frame's <this>, token identifies the method being invoked,
1125 i.e. is a (type id,slot #) pair, and impl address is the address of the method implementation.
1130 static const UINT16 INVALID_HASH = (UINT16)(-1);
1134 //read and write the cache keyed by (method table,token) pair.
1135 inline ResolveCacheElem* Lookup(size_t token, void* mt)
1136 { WRAPPER_NO_CONTRACT; return Lookup(token, INVALID_HASH, mt);}
1138 ResolveCacheElem* Lookup(size_t token, UINT16 tokenHash, void* mt);
1140 enum InsertKind {IK_NONE, IK_DISPATCH, IK_RESOLVE, IK_SHARED, IK_EXTERNAL};
1142 BOOL Insert(ResolveCacheElem* elem, InsertKind insertKind);
1144 void PromoteChainEntry(ResolveCacheElem* elem);
1147 // This is the heavyweight hashing algorithm. Use sparingly.
1148 static UINT16 HashToken(size_t token);
1150 inline void GetLoadFactor(size_t *total, size_t *used)
1152 LIMITED_METHOD_CONTRACT;
1154 *total = CALL_STUB_CACHE_SIZE;
1156 for (size_t i = 0; i < CALL_STUB_CACHE_SIZE; i++)
1157 if (cache[i] != empty)
1162 inline void *GetCacheBaseAddr()
1163 { LIMITED_METHOD_CONTRACT; return &cache[0]; }
1164 inline size_t GetCacheCount()
1165 { LIMITED_METHOD_CONTRACT; return CALL_STUB_CACHE_SIZE; }
1166 inline ResolveCacheElem *GetCacheEntry(size_t idx)
1167 { LIMITED_METHOD_CONTRACT; return VolatileLoad(&cache[idx]); }
1168 inline BOOL IsCacheEntryEmpty(size_t idx)
1169 { LIMITED_METHOD_CONTRACT; return cache[idx] == empty; }
1171 inline void SetCacheEntry(size_t idx, ResolveCacheElem *elem)
1173 LIMITED_METHOD_CONTRACT;
1175 cacheData[idx].numWrites++;
1178 CONSISTENCY_CHECK(m_writeLock.OwnedByCurrentThread());
1183 inline void ClearCacheEntry(size_t idx)
1185 LIMITED_METHOD_CONTRACT;
1187 cacheData[idx].numClears++;
1194 UINT32 insert_cache_external; //# of times Insert was called for IK_EXTERNAL
1195 UINT32 insert_cache_shared; //# of times Insert was called for IK_SHARED
1196 UINT32 insert_cache_dispatch; //# of times Insert was called for IK_DISPATCH
1197 UINT32 insert_cache_resolve; //# of times Insert was called for IK_RESOLVE
1198 UINT32 insert_cache_hit; //# of times Insert found an empty cache entry
1199 UINT32 insert_cache_miss; //# of times Insert already had a matching cache entry
1200 UINT32 insert_cache_collide; //# of times Insert found a used cache entry
1201 UINT32 insert_cache_write; //# of times Insert wrote a cache entry
1206 // Unlocked iterator of entries. Use only when read/write access to the cache
1207 // is safe. This would typically be at GC sync points, currently needed during
1208 // appdomain unloading.
1212 Iterator(DispatchCache *pCache);
1213 inline BOOL IsValid()
1214 { WRAPPER_NO_CONTRACT; return (m_curBucket < (INT32)m_pCache->GetCacheCount()); }
1216 // Unlink the current entry.
1217 // **NOTE** Using this method implicitly performs a call to Next to move
1218 // past the unlinked entry. Thus, one could accidentally skip
1219 // entries unless you take this into consideration.
1220 ResolveCacheElem *UnlinkEntry();
1221 inline ResolveCacheElem *Entry()
1222 { LIMITED_METHOD_CONTRACT; CONSISTENCY_CHECK(IsValid()); return *m_ppCurElem; }
1225 void NextValidBucket();
1226 inline void NextBucket()
1227 { LIMITED_METHOD_CONTRACT; m_curBucket++; m_ppCurElem = &m_pCache->cache[m_curBucket]; }
1229 DispatchCache *m_pCache;
1231 ResolveCacheElem **m_ppCurElem;
1239 //the following hash computation is also inlined in the resolve stub in asm (SO NO TOUCHIE)
1240 inline static UINT16 HashMT(UINT16 tokenHash, void* mt)
1242 LIMITED_METHOD_CONTRACT;
1246 size_t mtHash = (size_t) mt;
1247 mtHash = (((mtHash >> CALL_STUB_CACHE_NUM_BITS) + mtHash) >> LOG2_PTRSIZE) & CALL_STUB_CACHE_MASK;
1248 hash = (UINT16) mtHash;
1250 hash ^= (tokenHash & CALL_STUB_CACHE_MASK);
1255 ResolveCacheElem* cache[CALL_STUB_CACHE_SIZE]; //must be first
1256 ResolveCacheElem* empty; //empty entry, initialized to fail all comparisons
1259 struct CacheEntryData {
1263 CacheEntryData cacheData[CALL_STUB_CACHE_SIZE];
1264 #endif // STUB_LOGGING
1267 /**************************************************************************************************
1268 The hash tables are accessed via instances of the Prober. Prober is a probe into a bucket
1269 of the hash table, and therefore has an index which is the current probe position.
1270 It includes a count of the number of probes done in that bucket so far and a stride
1271 to step thru the bucket with. To do comparisons, it has a reference to an entry with which
1272 it can do comparisons (Equals(...)) of the entries (stubs) inside the hash table. It also has
1273 the key pair (keyA, keyB) that it is looking for.
1275 Typically, an entry of the appropriate type is created on the stack and then the prober is created passing
1276 in a reference to the entry. The prober is used for a complete operation, such as look for and find an
1277 entry (stub), creating and inserting it as necessary.
1279 The initial index and the stride are orthogonal hashes of the key pair, i.e. we are doing a variant of
1280 double hashing. When we initialize the prober (see FormHash below) we set the initial probe based on
1281 one hash. The stride (used as a modulo addition of the probe position) is based on a different hash and
1282 is such that it will vist every location in the bucket before repeating. Hence it is imperative that
1283 the bucket size and the stride be relative prime wrt each other. We have chosen to make bucket sizes
1284 a power of 2, so we force stride to be odd.
1286 Note -- it must be assumed that multiple probers are walking the same tables and buckets at the same time.
1287 Additionally, the counts may not be accurate, and there may be duplicates in the tables. Since the tables
1288 do not allow concurrent deletion, some of the concurrency issues are ameliorated.
1292 friend class FastTable;
1293 friend class BucketTable;
1295 Prober(Entry* e) {LIMITED_METHOD_CONTRACT; comparer = e;}
1296 //find the requested entry, if not there return CALL_STUB_EMPTY_ENTRY
1298 //add the entry into the bucket, if it is not already in the bucket.
1299 //return the entry actually in the bucket (existing or added)
1300 size_t Add(size_t entry);
1302 //return the bucket (FastTable*) that the prober is currently walking
1303 inline size_t* items() {LIMITED_METHOD_CONTRACT; return &base[-CALL_STUB_FIRST_INDEX];}
1304 //are there more probes possible, or have we probed everything in the bucket
1305 inline BOOL NoMore() {LIMITED_METHOD_CONTRACT; return probes>mask;} //both probes and mask are (-1)
1306 //advance the probe to a new place in the bucket
1309 WRAPPER_NO_CONTRACT;
1310 index = (index + stride) & mask;
1314 inline size_t Read()
1316 LIMITED_METHOD_CONTRACT;
1318 return VolatileLoad(&base[index]);
1320 //initialize a prober across a bucket (table) for the specified keys.
1321 void InitProber(size_t key1, size_t key2, size_t* table);
1322 //set up the initial index and stride and probe count
1323 inline void FormHash()
1325 LIMITED_METHOD_CONTRACT;
1328 //these two hash functions have not been formally measured for effectiveness
1329 //but they are at least orthogonal
1331 size_t a = ((keyA>>16) + keyA);
1332 size_t b = ((keyB>>16) ^ keyB);
1333 index = (((a*CALL_STUB_HASH_CONST1)>>4)+((b*CALL_STUB_HASH_CONST2)>>4)+CALL_STUB_HASH_CONST1) & mask;
1334 stride = ((a+(b*CALL_STUB_HASH_CONST1)+CALL_STUB_HASH_CONST2) | 1) & mask;
1336 //atomically grab an empty slot so we can insert a new entry into the bucket
1337 BOOL GrabEntry(size_t entryValue);
1338 size_t keyA; //key pair we are looking for
1340 size_t* base; //we have our own pointer to the bucket, so races don't matter.
1341 // We won't care if we do the lookup in an
1342 // outdated bucket (has grown out from under us).
1343 // All that will happen is possibly dropping an entry
1344 // on the floor or adding a duplicate.
1345 size_t index; //current probe point in the bucket
1346 size_t stride; //amount to step on each successive probe, must be relatively prime wrt the bucket size
1347 size_t mask; //size of bucket - 1
1348 size_t probes; //number probes - 1
1349 Entry* comparer;//used to compare an entry against the sought after key pair
1352 /********************************************************************************************************
1353 FastTable is used to implement the buckets of a BucketTable, a bucketized hash table. A FastTable is
1354 an array of entries (contents). The first two slots of contents store the size-1 and count of entries
1355 actually in the FastTable. Note that the count may be inaccurate and there may be duplicates. Careful
1356 attention must be paid to eliminate the need for interlocked or serialized or locked operations in face
1360 #pragma warning(push)
1361 #pragma warning(disable : 4200) // disable zero-sized array warning
1365 friend class BucketTable;
1368 FastTable() { LIMITED_METHOD_CONTRACT; }
1369 ~FastTable() { LIMITED_METHOD_CONTRACT; }
1371 //initialize a prober for the specified keys.
1372 inline BOOL SetUpProber(size_t keyA, size_t keyB, Prober* probe)
1382 probe->InitProber(keyA, keyB, &contents[0]);
1385 //find the requested entry (keys of prober), if not there return CALL_STUB_EMPTY_ENTRY
1386 size_t Find(Prober* probe);
1387 //add the entry, if it is not already there. Probe is used to search.
1388 //Return the entry actually contained (existing or added)
1389 size_t Add(size_t entry, Prober* probe);
1390 void IncrementCount();
1392 // Create a FastTable with space for numberOfEntries. Please note that this method
1393 // does not throw on OOM. **YOU MUST CHECK FOR NULL RETURN**
1394 static FastTable* MakeTable(size_t numberOfEntries)
1399 INJECT_FAULT(COMPlusThrowOM(););
1402 size_t size = CALL_STUB_MIN_ENTRIES;
1403 while (size < numberOfEntries) {size = size<<1;}
1404 // if (size == CALL_STUB_MIN_ENTRIES)
1406 FastTable* table = new (NumCallStubs, size) FastTable();
1407 table->InitializeContents(size);
1410 //Initialize as empty
1411 void InitializeContents(size_t size)
1413 LIMITED_METHOD_CONTRACT;
1414 memset(&contents[0], CALL_STUB_EMPTY_ENTRY, (size+CALL_STUB_FIRST_INDEX)*sizeof(BYTE*));
1415 contents[CALL_STUB_MASK_INDEX] = size-1;
1417 inline size_t tableMask() {LIMITED_METHOD_CONTRACT; return (size_t) (contents[CALL_STUB_MASK_INDEX]);}
1418 inline size_t tableSize() {LIMITED_METHOD_CONTRACT; return tableMask()+1;}
1419 inline size_t tableCount() {LIMITED_METHOD_CONTRACT; return (size_t) (contents[CALL_STUB_COUNT_INDEX]);}
1420 inline BOOL isFull()
1422 LIMITED_METHOD_CONTRACT;
1423 return (tableCount()+1) * 100 / CALL_STUB_LOAD_FACTOR >= tableSize();
1425 //we store (size-1) in bucket[CALL_STUB_MASK_INDEX==0],
1426 //we store the used count in bucket[CALL_STUB_COUNT_INDEX==1],
1427 //we have an unused cell to use as a temp at bucket[CALL_STUB_DEAD_LINK==2],
1428 //and the table starts at bucket[CALL_STUB_FIRST_INDEX==3],
1431 void* operator new(size_t) = delete;
1433 static struct NumCallStubs_t {} NumCallStubs;
1435 void* operator new(size_t baseSize, NumCallStubs_t, size_t numCallStubs)
1437 return ::operator new(baseSize + (numCallStubs + CALL_STUB_FIRST_INDEX) * sizeof(size_t));
1441 #pragma warning(pop)
1444 /******************************************************************************************************
1445 BucketTable is a bucketized hash table. It uses FastTables for its buckets. The hash tables
1446 used by the VirtualCallStubManager are BucketTables. The number of buckets is fixed at the time
1447 the table is created. The actual buckets are allocated as needed, and grow as necessary. The reason
1448 for using buckets is primarily to reduce the cost of growing, since only a single bucket is actually
1449 grown at any given time. Since the hash tables are accessed infrequently, the load factor that
1450 controls growth is quite high (90%). Since we use hashing to pick the bucket, and we use hashing to
1451 lookup inside the bucket, it is important that the hashing function used here is orthogonal to the ones
1452 used in the buckets themselves (see FastTable::FormHash).
1457 BucketTable(size_t numberOfBuckets)
1459 WRAPPER_NO_CONTRACT;
1460 size_t size = CALL_STUB_MIN_BUCKETS;
1461 while (size < numberOfBuckets) {size = size<<1;}
1462 buckets = AllocateBuckets(size);
1463 // Initialize statistics counters
1464 memset(&stats, 0, sizeof(stats));
1469 LIMITED_METHOD_CONTRACT;
1472 size_t size = bucketCount()+CALL_STUB_FIRST_INDEX;
1473 for(size_t ix = CALL_STUB_FIRST_INDEX; ix < size; ix++) delete (FastTable*)(buckets[ix]);
1478 //initialize a prober for the specified keys.
1479 BOOL SetUpProber(size_t keyA, size_t keyB, Prober *prober);
1480 //find the requested entry (keys of prober), if not there return CALL_STUB_EMPTY_ENTRY
1481 inline size_t Find(Prober* probe) {WRAPPER_NO_CONTRACT; return probe->Find();}
1482 //add the entry, if it is not already there. Probe is used to search.
1483 size_t Add(size_t entry, Prober* probe);
1484 //reclaim abandoned buckets. Buckets are abaondoned when they need to grow.
1485 //needs to be called inside a gc sync point.
1486 static void Reclaim();
1490 UINT32 bucket_space; //# of bytes in caches and tables, not including the stubs themselves
1491 UINT32 bucket_space_dead; //# of bytes of abandoned buckets not yet recycled.
1497 inline size_t bucketMask() {LIMITED_METHOD_CONTRACT; return (size_t) (buckets[CALL_STUB_MASK_INDEX]);}
1498 inline size_t bucketCount() {LIMITED_METHOD_CONTRACT; return bucketMask()+1;}
1499 inline size_t ComputeBucketIndex(size_t keyA, size_t keyB)
1501 LIMITED_METHOD_CONTRACT;
1502 size_t a = ((keyA>>16) + keyA);
1503 size_t b = ((keyB>>16) ^ keyB);
1504 return CALL_STUB_FIRST_INDEX+(((((a*CALL_STUB_HASH_CONST2)>>5)^((b*CALL_STUB_HASH_CONST1)>>5))+CALL_STUB_HASH_CONST2) & bucketMask());
1506 //grows the bucket referenced by probe.
1507 BOOL GetMoreSpace(const Prober* probe);
1508 //creates storage in which to store references to the buckets
1509 static size_t* AllocateBuckets(size_t size)
1511 LIMITED_METHOD_CONTRACT;
1512 size_t* buckets = new size_t[size+CALL_STUB_FIRST_INDEX];
1513 if (buckets != NULL)
1515 memset(&buckets[0], CALL_STUB_EMPTY_ENTRY, (size+CALL_STUB_FIRST_INDEX)*sizeof(void*));
1516 buckets[CALL_STUB_MASK_INDEX] = size-1;
1520 inline size_t Read(size_t index)
1522 LIMITED_METHOD_CONTRACT;
1523 CONSISTENCY_CHECK(index <= bucketMask()+CALL_STUB_FIRST_INDEX);
1524 return VolatileLoad(&buckets[index]);
1526 inline void Write(size_t index, size_t value)
1528 LIMITED_METHOD_CONTRACT;
1529 CONSISTENCY_CHECK(index <= bucketMask()+CALL_STUB_FIRST_INDEX);
1530 VolatileStore(&buckets[index], value);
1533 // We store (#buckets-1) in bucket[CALL_STUB_MASK_INDEX ==0]
1534 // We have two unused cells at bucket[CALL_STUB_COUNT_INDEX ==1]
1535 // and bucket[CALL_STUB_DEAD_LINK ==2]
1536 // and the table starts at bucket[CALL_STUB_FIRST_INDEX ==3]
1537 // the number of elements is bucket[CALL_STUB_MASK_INDEX]+CALL_STUB_FIRST_INDEX
1539 static FastTable* dead; //linked list head of to be deleted (abandoned) buckets
1543 #endif // !_VIRTUAL_CALL_STUB_H