diff options
Diffstat (limited to 'src/vm/inlinetracking.h')
| -rw-r--r-- | src/vm/inlinetracking.h | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/src/vm/inlinetracking.h b/src/vm/inlinetracking.h new file mode 100644 index 0000000000..cf05027785 --- /dev/null +++ b/src/vm/inlinetracking.h @@ -0,0 +1,232 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. +// ============================================================================================= +// Definitions for tracking method inlinings in NGen images. +// The only information stored is "who" got inlined "where", no offsets or inlining depth tracking. +// (No good for debugger yet.) +// This information is later exposed to profilers and can be useful for ReJIT. +// Runtime inlining is not being tracked because profilers can deduce it via callbacks anyway. +// ============================================================================================= +#ifndef INLINETRACKING_H_ +#define INLINETRACKING_H_ +#include "corhdr.h" +#include "shash.h" +#include "sarray.h" +#include "crsttypes.h" +#include "daccess.h" + +class MethodDesc; +typedef DPTR(class MethodDesc) PTR_MethodDesc; + +struct MethodInModule +{ + Module *m_module; + mdMethodDef m_methodDef; + + bool operator <(const MethodInModule& other) const; + + bool operator ==(const MethodInModule& other) const; + + bool operator !=(const MethodInModule& other) const; + + MethodInModule(Module * module, mdMethodDef methodDef) + :m_module(module), m_methodDef(methodDef) + { + LIMITED_METHOD_DAC_CONTRACT; + } + + MethodInModule() + :m_module(NULL), m_methodDef(0) + { + LIMITED_METHOD_DAC_CONTRACT; + } + +}; + +struct InlineTrackingEntry +{ + MethodInModule m_inlinee; + + //Our research shows that 70% of methods are inlined less than 4 times + //so it's probably worth to inline enough storage for 3 inlines. + InlineSArray<MethodInModule, 3> m_inliners; + + + // SArray and SBuffer don't have sane implementations for operator= + // but SHash uses operator= for moving values, so we have to provide + // implementations that don't corrupt memory. + InlineTrackingEntry(const InlineTrackingEntry& other); + InlineTrackingEntry &operator=(const InlineTrackingEntry &other); + + InlineTrackingEntry() + { + WRAPPER_NO_CONTRACT; + } + + void Add(PTR_MethodDesc inliner); + void SortAndDeduplicate(); +}; + +class InlineTrackingMapTraits : public NoRemoveSHashTraits <DefaultSHashTraits<InlineTrackingEntry> > +{ +public: + typedef MethodInModule key_t; + + static key_t GetKey(const element_t &e) + { + LIMITED_METHOD_DAC_CONTRACT; + return e.m_inlinee; + } + static BOOL Equals(key_t k1, key_t k2) + { + LIMITED_METHOD_DAC_CONTRACT; + return (k1 == k2); + } + static count_t Hash(key_t k) + { + LIMITED_METHOD_DAC_CONTRACT; + return ((count_t)k.m_methodDef ^ (count_t)k.m_module); + } + static const element_t Null() + { + LIMITED_METHOD_DAC_CONTRACT; + InlineTrackingEntry e; + return e; + } + static bool IsNull(const element_t &e) + { + LIMITED_METHOD_DAC_CONTRACT; + return !e.m_inlinee.m_module; + } + + static const bool s_NoThrow = false; +}; + +// This is a hashtable that is used by each module to track inlines in the code inside this module. +// For each key (MethodInModule) it stores an array of methods (MethodInModule), each of those methods +// directly or indirectly inlined code from MethodInModule specified by the key. +// +// It is important to understand that even though each module has an its own instance of the map, +// map can had methods from other modules both as keys and values. +// - If module has code inlined from other modules we naturally get methods from other modules as keys in the map. +// - During NGgen process, modules can generate code for generic classes and methods from other modules and +// embed them into the image (like List<MyStruct>.FindAll() might get embeded into module of MyStruct). +// In such cases values of the map can belong to other modules. +// +// Currently this map is created and updated by modules only during native image generation +// and later saved as PersistentInlineTrackingMap. +class InlineTrackingMap : public SHash < InlineTrackingMapTraits > +{ +private: + Crst m_mapCrst; + +public: + InlineTrackingMap(); + void AddInlining(MethodDesc *inliner, MethodDesc *inlinee); +}; + +typedef DPTR(InlineTrackingMap) PTR_InlineTrackingMap; + +// This is a persistent map that is stored inside each NGen-ed module image and is used to track +// inlines in the NGEN-ed code inside this module. +// At runtime this map is used by profiler to track methods that inline a given method, +// thus answering a question "give me all methods from this native image that has code from this method?" +// It doesn't require any load time unpacking and serves requests directly from NGEN image. +// +// It is composed of two arrays: +// m_inlineeIndex - sorted (by InlineeRecord.key i.e. by module then token) array of InlineeRecords, given an inlinee module name hash (8 bits) +// and a method token (24 bits) we use binary search to find if this method has ever been inlined in NGen-ed code of this image. +// Each record has m_offset, which is an offset inside m_inlinersBuffer, it has more data on where the method got inlined. +// +// It is totally possible to have more than one InlineeRecords with the same key, not only due hash collision, but also due to +// the fact that we create one record for each (inlinee module / inliner module) pair. +// For example: we have MyModule!MyType that uses mscorlib!List<T>. Let's say List<T>.ctor got inlined into +// MyType.GetAllThinds() and into List<MyType>.FindAll. In this case we'll have two InlineeRecords for mscorlib!List<T>.ctor +// one for MyModule and another one for mscorlib. +// PersistentInlineTrackingMap.GetInliners() always reads all InlineeRecords as long as they have the same key, few of them filtered out as hash collisions +// others provide legitimate inlining information for methods from different modules. +// +// m_inlinersBuffer - byte array compressed by NibbleWriter. At any valid offset taken from InlineeRecord from m_inlineeIndex, there is a compressed chunk +// of this format: +// [InlineeModuleZapIndex][InlinerModuleZapIndex] [N - # of following inliners] [#1 inliner method RID] ... [#N inliner method RID] +// [InlineeModuleZapIndex] is used to verify that we actually found a desired inlinee module (not just a name hash collision). +// [InlinerModuleZapIndex] is an index of a module that owns following method tokens (inliners) +// [1..N inliner RID] are the sorted diff compressed method RIDs from the module specified by InlinerModuleZapIndex, +// those methods directly or indirectly inlined code from inlinee method specified by InlineeRecord. +// Since all the RIDs are sorted we'are actually able to save some space by using diffs instead of values, because NibbleWriter +// is good at saving small numbers. +// For example for RIDs: 5, 6, 19, 25, 30, we'll write: 5, 1 (=6-5), 13 (=19-6), 6 (=25-19), 5 (=30-25) +// +// m_inlineeIndex +// +-----+-----+--------------------------------------------------+-----+-----+ +// | - | - | m_key {module name hash, method token); m_offset | - | - | +// +-----+-----+--------------------------------------------|-----+-----+-----+ +// | +// +-----------------------------------+ +// | +// m_inlinersBuffer \-/ +// +-----------------+-----------------------+------------------------+------------------------+------+------+--------+------+-------------+ +// | - - - | InlineeModuleZapIndex | InlinerModuleZapIndex | SavedInlinersCount (N) | rid1 | rid2 | ...... | ridN | - - - | +// +-----------------+-----------------------+------------------------+------------------------+------+------+--------+------+-------------+ +// +class PersistentInlineTrackingMap +{ +private: + struct InlineeRecord + { + DWORD m_key; + DWORD m_offset; + + InlineeRecord() + : m_key(0) + { + LIMITED_METHOD_CONTRACT; + } + + InlineeRecord(RID rid, LPCUTF8 simpleName); + + bool operator <(const InlineeRecord& other) const + { + LIMITED_METHOD_DAC_CONTRACT; + return m_key < other.m_key; + } + + bool operator ==(const InlineeRecord& other) const + { + LIMITED_METHOD_DAC_CONTRACT; + return m_key == other.m_key; + } + }; + typedef DPTR(InlineeRecord) PTR_InlineeRecord; + + PTR_Module m_module; + + PTR_InlineeRecord m_inlineeIndex; + DWORD m_inlineeIndexSize; + + PTR_BYTE m_inlinersBuffer; + DWORD m_inlinersBufferSize; + +public: + + PersistentInlineTrackingMap(Module *module) + : m_module(dac_cast<PTR_Module>(module)) + { + LIMITED_METHOD_CONTRACT; + _ASSERTE(module != NULL); + } + + void Save(DataImage *image, InlineTrackingMap* runtimeMap); + void Fixup(DataImage *image); + + COUNT_T GetInliners(PTR_Module inlineeOwnerMod, mdMethodDef inlineeTkn, COUNT_T inlinersSize, MethodInModule inliners[], BOOL *incompleteData); + +private: + void ProcessInlineTrackingEntry(DataImage *image, SBuffer *inlinersBuffer, SArray<InlineeRecord> *inlineeIndex, InlineTrackingEntry *entry); + Module *GetModuleByIndex(DWORD index); +}; + +typedef DPTR(PersistentInlineTrackingMap) PTR_PersistentInlineTrackingMap; + +#endif //INLINETRACKING_H_ |