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// Definitions for tracking method inlinings in NGen and R2R images.
6// The only information stored is "who" got inlined "where", no offsets or inlining depth tracking.
7// (No good for debugger yet.)
8// This information is later exposed to profilers and can be useful for ReJIT.
9// Runtime inlining is not being tracked because profilers can deduce it via callbacks anyway.
10//
11// This file is made of two major component groups:
12// a) InlineTrackingMap - This is a compilation time datastructure that holds an uncompressed
13// version of the inline tracking information. It is appended to as methods are compiled.
14// MethodInModule, InlineTrackingEntry, InlineTrackingMapTraits are all support infratsructure
15// in this group.
16//
17// b) PersistentInlineTrackingMap[R2R/NGen] - These are the types that understand the image persistence
18// formats. At the end of image compilation one of them consumes all the data from an
19// InlineTrackingMap to encode it. At runtime an instance will be constructed to read back
20// the encoded data on demand. PersistantInlineTrackingMapR2R and PersistantInlineTrackingMapNGen
21// would nominally use a common base type or interface, but due to ngen binary serialization vtables
22// were avoided. See farther below for the different format descriptions.
23// =============================================================================================
24
25#ifndef INLINETRACKING_H_
26#define INLINETRACKING_H_
27#include "corhdr.h"
28#include "shash.h"
29#include "sarray.h"
30#include "crsttypes.h"
31#include "daccess.h"
32
33
34
35// ---------------------------------- Compile time support ----------------------------------------------
36
37class MethodDesc;
38typedef DPTR(class MethodDesc) PTR_MethodDesc;
39
40class ZapHeap;
41
42struct MethodInModule
43{
44 Module *m_module;
45 mdMethodDef m_methodDef;
46
47 bool operator <(const MethodInModule& other) const;
48
49 bool operator ==(const MethodInModule& other) const;
50
51 bool operator !=(const MethodInModule& other) const;
52
53 MethodInModule(Module * module, mdMethodDef methodDef)
54 :m_module(module), m_methodDef(methodDef)
55 {
56 LIMITED_METHOD_DAC_CONTRACT;
57 }
58
59 MethodInModule()
60 :m_module(NULL), m_methodDef(0)
61 {
62 LIMITED_METHOD_DAC_CONTRACT;
63 }
64
65};
66
67struct InlineTrackingEntry
68{
69 MethodInModule m_inlinee;
70
71 //Our research shows that 70% of methods are inlined less than 4 times
72 //so it's probably worth to inline enough storage for 3 inlines.
73 InlineSArray<MethodInModule, 3> m_inliners;
74
75
76 // SArray and SBuffer don't have sane implementations for operator=
77 // but SHash uses operator= for moving values, so we have to provide
78 // implementations that don't corrupt memory.
79 InlineTrackingEntry(const InlineTrackingEntry& other);
80 InlineTrackingEntry &operator=(const InlineTrackingEntry &other);
81
82 InlineTrackingEntry()
83 {
84 WRAPPER_NO_CONTRACT;
85 }
86
87 void Add(PTR_MethodDesc inliner);
88 void SortAndDeduplicate();
89};
90
91class InlineTrackingMapTraits : public NoRemoveSHashTraits <DefaultSHashTraits<InlineTrackingEntry> >
92{
93public:
94 typedef MethodInModule key_t;
95
96 static key_t GetKey(const element_t &e)
97 {
98 LIMITED_METHOD_DAC_CONTRACT;
99 return e.m_inlinee;
100 }
101 static BOOL Equals(key_t k1, key_t k2)
102 {
103 LIMITED_METHOD_DAC_CONTRACT;
104 return (k1 == k2);
105 }
106 static count_t Hash(key_t k)
107 {
108 LIMITED_METHOD_DAC_CONTRACT;
109 return ((count_t)k.m_methodDef ^ (count_t)k.m_module);
110 }
111 static const element_t Null()
112 {
113 LIMITED_METHOD_DAC_CONTRACT;
114 InlineTrackingEntry e;
115 return e;
116 }
117 static bool IsNull(const element_t &e)
118 {
119 LIMITED_METHOD_DAC_CONTRACT;
120 return !e.m_inlinee.m_module;
121 }
122
123 static const bool s_NoThrow = false;
124};
125
126// This is a hashtable that is used by each module to track inlines in the code inside this module.
127// For each key (MethodInModule) it stores an array of methods (MethodInModule), each of those methods
128// directly or indirectly inlined code from MethodInModule specified by the key.
129//
130// It is important to understand that even though each module has an its own instance of the map,
131// map can had methods from other modules both as keys and values.
132// - If module has code inlined from other modules we naturally get methods from other modules as keys in the map.
133// - During NGgen process, modules can generate code for generic classes and methods from other modules and
134// embed them into the image (like List<MyStruct>.FindAll() might get embeded into module of MyStruct).
135// In such cases values of the map can belong to other modules.
136//
137// Currently this map is created and updated by modules only during native image generation
138// and later saved as PersistentInlineTrackingMap.
139class InlineTrackingMap : public SHash < InlineTrackingMapTraits >
140{
141private:
142 Crst m_mapCrst;
143
144public:
145 InlineTrackingMap();
146 void AddInlining(MethodDesc *inliner, MethodDesc *inlinee);
147};
148
149typedef DPTR(InlineTrackingMap) PTR_InlineTrackingMap;
150
151
152
153
154// ------------------------------------ Persistance support ----------------------------------------------------------
155
156
157
158
159
160// NGEN format
161//
162// This is a persistent map that is stored inside each NGen-ed module image and is used to track
163// inlines in the NGEN-ed code inside this module.
164// At runtime this map is used by profiler to track methods that inline a given method,
165// thus answering a question "give me all methods from this native image that has code from this method?"
166// It doesn't require any load time unpacking and serves requests directly from NGEN image.
167//
168// It is composed of two arrays:
169// m_inlineeIndex - sorted (by ZapInlineeRecord.key i.e. by module then token) array of ZapInlineeRecords, given an inlinee module name hash (8 bits)
170// 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.
171// Each record has m_offset, which is an offset inside m_inlinersBuffer, it has more data on where the method got inlined.
172//
173// It is totally possible to have more than one ZapInlineeRecords with the same key, not only due hash collision, but also due to
174// the fact that we create one record for each (inlinee module / inliner module) pair.
175// For example: we have MyModule!MyType that uses mscorlib!List<T>. Let's say List<T>.ctor got inlined into
176// MyType.GetAllThinds() and into List<MyType>.FindAll. In this case we'll have two InlineeRecords for mscorlib!List<T>.ctor
177// one for MyModule and another one for mscorlib.
178// PersistentInlineTrackingMap.GetInliners() always reads all ZapInlineeRecords as long as they have the same key, few of them filtered out
179// as hash collisions others provide legitimate inlining information for methods from different modules.
180//
181// m_inlinersBuffer - byte array compressed by NibbleWriter. At any valid offset taken from ZapInlineeRecord from m_inlineeIndex, there is a compressed chunk
182// of this format:
183// [InlineeModuleZapIndex][InlinerModuleZapIndex] [N - # of following inliners] [#1 inliner method RID] ... [#N inliner method RID]
184// [InlineeModuleZapIndex] is used to verify that we actually found a desired inlinee module (not just a name hash collision).
185// [InlinerModuleZapIndex] is an index of a module that owns following method tokens (inliners)
186// [1..N inliner RID] are the sorted diff compressed method RIDs from the module specified by InlinerModuleZapIndex,
187// those methods directly or indirectly inlined code from inlinee method specified by ZapInlineeRecord.
188// Since all the RIDs are sorted we'are actually able to save some space by using diffs instead of values, because NibbleWriter
189// is good at saving small numbers.
190// 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)
191//
192// m_inlineeIndex
193// +-----+-----+--------------------------------------------------+-----+-----+
194// | - | - | m_key {module name hash, method token); m_offset | - | - |
195// +-----+-----+--------------------------------------------|-----+-----+-----+
196// |
197// +-----------------------------------+
198// |
199// m_inlinersBuffer \-/
200// +-----------------+-----------------------+------------------------+------------------------+------+------+--------+------+-------------+
201// | - - - | InlineeModuleZapIndex | InlinerModuleZapIndex | SavedInlinersCount (N) | rid1 | rid2 | ...... | ridN | - - - |
202// +-----------------+-----------------------+------------------------+------------------------+------+------+--------+------+-------------+
203//
204
205
206
207
208
209
210
211
212
213// R2R encoding variation for the map
214//
215// It has several differences from the NGEN encoding. NGEN refers to methods outside the current assembly via module index + foreign module's token
216// but R2R can't take those fragile dependencies. Instead we refer to all methods via MethodDef tokens in the current assembly's metadata. This
217// is sufficient for everything we need to track now but in the future we may need to upgrade to a more expressive encoding. Currently NonVersionable
218// attributed methods may be inlined but will not be tracked. This shows up as a known limitation in the profiler APIs that expose this data.
219//
220// The format changes from NGEN:
221// a) The InlineIndex uses a MethodDef RID token as the key.
222// b) InlineeModuleZapIndex is omitted because the module is always the current one being compiled.
223// c) InlinerModuleZapIndex is similarly omitted.
224// d) (a), (b) and (c) together imply there is at most one entry in the inlineeIndex for any given key
225// e) A trivial header is now explicitly described
226//
227//
228// The resulting serialized format is a sequence of blobs:
229// 1) Header (4 byte aligned)
230// short MajorVersion - currently set to 1, increment on breaking change
231// short MinorVersion - currently set to 0, increment on non-breaking format addition
232// int SizeOfInlineIndex - size in bytes of the inline index
233//
234// 2) InlineIndex - Immediately following header. This is a sorted (by ZapInlineeRecord.key) array of ZapInlineeRecords, given a method token (32 bits)
235// we use binary search to find if this method has ever been inlined in R2R code of this image. Each record has m_offset, which is
236// an offset inside InlinersBuffer, it has more data on where the method got inlined. There is at most one ZapInlineeRecord with the
237// same key.
238//
239// 3) InlinersBuffer - Located immediately following the InlineIndex (Header RVA + sizeof(Header) + header.SizeOfInlineIndex)
240// This is a byte array compressed by NibbleWriter. At any valid offset taken from ZapInlineeRecord from InlineeIndex, there is a
241// compressed chunk of this format:
242// [N - # of following inliners] [#1 inliner method RID] ... [#N inliner method RID]
243// [1..N inliner RID] are the sorted diff compressed method RIDs interpreted as MethodDefs in this assembly's metadata,
244// Those methods directly or indirectly inlined code from inlinee method specified by ZapInlineeRecord.
245// Since all the RIDs are sorted we'are actually able to save some space by using diffs instead of values, because NibbleWriter
246// is good at saving small numbers.
247// 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)
248//
249// InlineeIndex
250// +-----+-----+---------------------------------------+-----+-----+
251// | - | - | m_key {MethodDefToken); m_offset | - | - |
252// +-----+-----+---------------------------------|-----+-----+-----+
253// |
254// +--------------------------+
255// |
256// InlinersBuffer \-/
257// +-----------------+------------------------+------+------+--------+------+-------------+
258// | - - - | SavedInlinersCount (N) | rid1 | rid2 | ...... | ridN | - - - |
259// +-----------------+------------------------+------+------+--------+------+-------------+
260//
261
262
263
264//A common key format for R2R and NGEN. If the formats
265//diverge further this might become irrelevant
266struct ZapInlineeRecord
267{
268 DWORD m_key;
269 DWORD m_offset;
270
271 ZapInlineeRecord()
272 : m_key(0)
273 {
274 LIMITED_METHOD_CONTRACT;
275 }
276
277 void InitForR2R(RID rid)
278 {
279 LIMITED_METHOD_CONTRACT;
280 m_key = rid;
281 }
282
283 void InitForNGen(RID rid, LPCUTF8 simpleName);
284
285 bool operator <(const ZapInlineeRecord& other) const
286 {
287 LIMITED_METHOD_DAC_CONTRACT;
288 return m_key < other.m_key;
289 }
290
291 bool operator ==(const ZapInlineeRecord& other) const
292 {
293 LIMITED_METHOD_DAC_CONTRACT;
294 return m_key == other.m_key;
295 }
296};
297
298typedef DPTR(ZapInlineeRecord) PTR_ZapInlineeRecord;
299
300
301// This type knows how to serialize and deserialize the inline tracking map format within an NGEN image. See
302// above for a description of the format.
303class PersistentInlineTrackingMapNGen
304{
305private:
306 PTR_Module m_module;
307
308 PTR_ZapInlineeRecord m_inlineeIndex;
309 DWORD m_inlineeIndexSize;
310
311 PTR_BYTE m_inlinersBuffer;
312 DWORD m_inlinersBufferSize;
313
314public:
315
316 PersistentInlineTrackingMapNGen(Module *module)
317 : m_module(dac_cast<PTR_Module>(module))
318 {
319 LIMITED_METHOD_CONTRACT;
320 _ASSERTE(module != NULL);
321 }
322
323 // runtime deserialization
324 COUNT_T GetInliners(PTR_Module inlineeOwnerMod, mdMethodDef inlineeTkn, COUNT_T inlinersSize, MethodInModule inliners[], BOOL *incompleteData);
325
326 // compile-time serialization
327#ifndef DACCESS_COMPILE
328 void Save(DataImage *image, InlineTrackingMap* runtimeMap);
329 void Fixup(DataImage *image);
330
331private:
332#endif
333
334 Module *GetModuleByIndex(DWORD index);
335
336};
337
338typedef DPTR(PersistentInlineTrackingMapNGen) PTR_PersistentInlineTrackingMapNGen;
339
340
341// This type knows how to serialize and deserialize the inline tracking map format within an R2R image. See
342// above for a description of the format.
343#ifdef FEATURE_READYTORUN
344class PersistentInlineTrackingMapR2R
345{
346private:
347 PTR_Module m_module;
348
349 PTR_ZapInlineeRecord m_inlineeIndex;
350 DWORD m_inlineeIndexSize;
351
352 PTR_BYTE m_inlinersBuffer;
353 DWORD m_inlinersBufferSize;
354
355public:
356
357 // runtime deserialization
358#ifndef DACCESS_COMPILE
359 static BOOL TryLoad(Module* pModule, const BYTE* pBuffer, DWORD cbBuffer, AllocMemTracker *pamTracker, PersistentInlineTrackingMapR2R** ppLoadedMap);
360#endif
361 COUNT_T GetInliners(PTR_Module inlineeOwnerMod, mdMethodDef inlineeTkn, COUNT_T inlinersSize, MethodInModule inliners[], BOOL *incompleteData);
362
363
364 // compile time serialization
365#ifndef DACCESS_COMPILE
366 static void Save(ZapHeap* pHeap, SBuffer *saveTarget, InlineTrackingMap* runtimeMap);
367#endif
368
369};
370
371typedef DPTR(PersistentInlineTrackingMapR2R) PTR_PersistentInlineTrackingMapR2R;
372#endif //FEATURE_READYTORUN
373
374
375#endif //INLINETRACKING_H_
376