File: | build/source/bolt/runtime/instr.cpp |
Warning: | line 1190, column 25 Array access (via field 'EdgeFreqs') results in a null pointer dereference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- bolt/runtime/instr.cpp ---------------------------------------------===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // BOLT runtime instrumentation library for x86 Linux. Currently, BOLT does | |||
10 | // not support linking modules with dependencies on one another into the final | |||
11 | // binary (TODO?), which means this library has to be self-contained in a single | |||
12 | // module. | |||
13 | // | |||
14 | // All extern declarations here need to be defined by BOLT itself. Those will be | |||
15 | // undefined symbols that BOLT needs to resolve by emitting these symbols with | |||
16 | // MCStreamer. Currently, Passes/Instrumentation.cpp is the pass responsible | |||
17 | // for defining the symbols here and these two files have a tight coupling: one | |||
18 | // working statically when you run BOLT and another during program runtime when | |||
19 | // you run an instrumented binary. The main goal here is to output an fdata file | |||
20 | // (BOLT profile) with the instrumentation counters inserted by the static pass. | |||
21 | // Counters for indirect calls are an exception, as we can't know them | |||
22 | // statically. These counters are created and managed here. To allow this, we | |||
23 | // need a minimal framework for allocating memory dynamically. We provide this | |||
24 | // with the BumpPtrAllocator class (not LLVM's, but our own version of it). | |||
25 | // | |||
26 | // Since this code is intended to be inserted into any executable, we decided to | |||
27 | // make it standalone and do not depend on any external libraries (i.e. language | |||
28 | // support libraries, such as glibc or stdc++). To allow this, we provide a few | |||
29 | // light implementations of common OS interacting functionalities using direct | |||
30 | // syscall wrappers. Our simple allocator doesn't manage deallocations that | |||
31 | // fragment the memory space, so it's stack based. This is the minimal framework | |||
32 | // provided here to allow processing instrumented counters and writing fdata. | |||
33 | // | |||
34 | // In the C++ idiom used here, we never use or rely on constructors or | |||
35 | // destructors for global objects. That's because those need support from the | |||
36 | // linker in initialization/finalization code, and we want to keep our linker | |||
37 | // very simple. Similarly, we don't create any global objects that are zero | |||
38 | // initialized, since those would need to go .bss, which our simple linker also | |||
39 | // don't support (TODO?). | |||
40 | // | |||
41 | //===----------------------------------------------------------------------===// | |||
42 | ||||
43 | #if defined (__x86_64__1) | |||
44 | #include "common.h" | |||
45 | ||||
46 | // Enables a very verbose logging to stderr useful when debugging | |||
47 | //#define ENABLE_DEBUG | |||
48 | ||||
49 | #ifdef ENABLE_DEBUG | |||
50 | #define DEBUG(X){} \ | |||
51 | { X; } | |||
52 | #else | |||
53 | #define DEBUG(X){} \ | |||
54 | {} | |||
55 | #endif | |||
56 | ||||
57 | #pragma GCC visibility push(hidden) | |||
58 | ||||
59 | extern "C" { | |||
60 | ||||
61 | #if defined(__APPLE__) | |||
62 | extern uint64_t* _bolt_instr_locations_getter(); | |||
63 | extern uint32_t _bolt_num_counters_getter(); | |||
64 | ||||
65 | extern uint8_t* _bolt_instr_tables_getter(); | |||
66 | extern uint32_t _bolt_instr_num_funcs_getter(); | |||
67 | ||||
68 | #else | |||
69 | ||||
70 | // Main counters inserted by instrumentation, incremented during runtime when | |||
71 | // points of interest (locations) in the program are reached. Those are direct | |||
72 | // calls and direct and indirect branches (local ones). There are also counters | |||
73 | // for basic block execution if they are a spanning tree leaf and need to be | |||
74 | // counted in order to infer the execution count of other edges of the CFG. | |||
75 | extern uint64_t __bolt_instr_locations[]; | |||
76 | extern uint32_t __bolt_num_counters; | |||
77 | // Descriptions are serialized metadata about binary functions written by BOLT, | |||
78 | // so we have a minimal understanding about the program structure. For a | |||
79 | // reference on the exact format of this metadata, see *Description structs, | |||
80 | // Location, IntrumentedNode and EntryNode. | |||
81 | // Number of indirect call site descriptions | |||
82 | extern uint32_t __bolt_instr_num_ind_calls; | |||
83 | // Number of indirect call target descriptions | |||
84 | extern uint32_t __bolt_instr_num_ind_targets; | |||
85 | // Number of function descriptions | |||
86 | extern uint32_t __bolt_instr_num_funcs; | |||
87 | // Time to sleep across dumps (when we write the fdata profile to disk) | |||
88 | extern uint32_t __bolt_instr_sleep_time; | |||
89 | // Do not clear counters across dumps, rewrite file with the updated values | |||
90 | extern bool __bolt_instr_no_counters_clear; | |||
91 | // Wait until all forks of instrumented process will finish | |||
92 | extern bool __bolt_instr_wait_forks; | |||
93 | // Filename to dump data to | |||
94 | extern char __bolt_instr_filename[]; | |||
95 | // Instumented binary file path | |||
96 | extern char __bolt_instr_binpath[]; | |||
97 | // If true, append current PID to the fdata filename when creating it so | |||
98 | // different invocations of the same program can be differentiated. | |||
99 | extern bool __bolt_instr_use_pid; | |||
100 | // Functions that will be used to instrument indirect calls. BOLT static pass | |||
101 | // will identify indirect calls and modify them to load the address in these | |||
102 | // trampolines and call this address instead. BOLT can't use direct calls to | |||
103 | // our handlers because our addresses here are not known at analysis time. We | |||
104 | // only support resolving dependencies from this file to the output of BOLT, | |||
105 | // *not* the other way around. | |||
106 | // TODO: We need better linking support to make that happen. | |||
107 | extern void (*__bolt_ind_call_counter_func_pointer)(); | |||
108 | extern void (*__bolt_ind_tailcall_counter_func_pointer)(); | |||
109 | // Function pointers to init/fini trampoline routines in the binary, so we can | |||
110 | // resume regular execution of these functions that we hooked | |||
111 | extern void __bolt_start_trampoline(); | |||
112 | extern void __bolt_fini_trampoline(); | |||
113 | ||||
114 | #endif | |||
115 | } | |||
116 | ||||
117 | namespace { | |||
118 | ||||
119 | /// A simple allocator that mmaps a fixed size region and manages this space | |||
120 | /// in a stack fashion, meaning you always deallocate the last element that | |||
121 | /// was allocated. In practice, we don't need to deallocate individual elements. | |||
122 | /// We monotonically increase our usage and then deallocate everything once we | |||
123 | /// are done processing something. | |||
124 | class BumpPtrAllocator { | |||
125 | /// This is written before each allocation and act as a canary to detect when | |||
126 | /// a bug caused our program to cross allocation boundaries. | |||
127 | struct EntryMetadata { | |||
128 | uint64_t Magic; | |||
129 | uint64_t AllocSize; | |||
130 | }; | |||
131 | ||||
132 | public: | |||
133 | void *allocate(size_t Size) { | |||
134 | Lock L(M); | |||
135 | ||||
136 | if (StackBase == nullptr) { | |||
137 | #if defined(__APPLE__) | |||
138 | int MAP_PRIVATE_MAP_ANONYMOUS = 0x1002; | |||
139 | #else | |||
140 | int MAP_PRIVATE_MAP_ANONYMOUS = 0x22; | |||
141 | #endif | |||
142 | StackBase = reinterpret_cast<uint8_t *>( | |||
143 | __mmap(0, MaxSize, 0x3 /* PROT_READ | PROT_WRITE*/, | |||
144 | Shared ? 0x21 /*MAP_SHARED | MAP_ANONYMOUS*/ | |||
145 | : MAP_PRIVATE_MAP_ANONYMOUS /* MAP_PRIVATE | MAP_ANONYMOUS*/, | |||
146 | -1, 0)); | |||
147 | StackSize = 0; | |||
148 | } | |||
149 | ||||
150 | Size = alignTo(Size + sizeof(EntryMetadata), 16); | |||
151 | uint8_t *AllocAddress = StackBase + StackSize + sizeof(EntryMetadata); | |||
152 | auto *M = reinterpret_cast<EntryMetadata *>(StackBase + StackSize); | |||
153 | M->Magic = Magic; | |||
154 | M->AllocSize = Size; | |||
155 | StackSize += Size; | |||
156 | assert(StackSize < MaxSize, "allocator ran out of memory"); | |||
157 | return AllocAddress; | |||
158 | } | |||
159 | ||||
160 | #ifdef DEBUG | |||
161 | /// Element-wise deallocation is only used for debugging to catch memory | |||
162 | /// bugs by checking magic bytes. Ordinarily, we reset the allocator once | |||
163 | /// we are done with it. Reset is done with clear(). There's no need | |||
164 | /// to deallocate each element individually. | |||
165 | void deallocate(void *Ptr) { | |||
166 | Lock L(M); | |||
167 | uint8_t MetadataOffset = sizeof(EntryMetadata); | |||
168 | auto *M = reinterpret_cast<EntryMetadata *>( | |||
169 | reinterpret_cast<uint8_t *>(Ptr) - MetadataOffset); | |||
170 | const uint8_t *StackTop = StackBase + StackSize + MetadataOffset; | |||
171 | // Validate size | |||
172 | if (Ptr != StackTop - M->AllocSize) { | |||
173 | // Failed validation, check if it is a pointer returned by operator new [] | |||
174 | MetadataOffset += | |||
175 | sizeof(uint64_t); // Space for number of elements alloc'ed | |||
176 | M = reinterpret_cast<EntryMetadata *>(reinterpret_cast<uint8_t *>(Ptr) - | |||
177 | MetadataOffset); | |||
178 | // Ok, it failed both checks if this assertion fails. Stop the program, we | |||
179 | // have a memory bug. | |||
180 | assert(Ptr == StackTop - M->AllocSize, | |||
181 | "must deallocate the last element alloc'ed"); | |||
182 | } | |||
183 | assert(M->Magic == Magic, "allocator magic is corrupt"); | |||
184 | StackSize -= M->AllocSize; | |||
185 | } | |||
186 | #else | |||
187 | void deallocate(void *) {} | |||
188 | #endif | |||
189 | ||||
190 | void clear() { | |||
191 | Lock L(M); | |||
192 | StackSize = 0; | |||
193 | } | |||
194 | ||||
195 | /// Set mmap reservation size (only relevant before first allocation) | |||
196 | void setMaxSize(uint64_t Size) { MaxSize = Size; } | |||
197 | ||||
198 | /// Set mmap reservation privacy (only relevant before first allocation) | |||
199 | void setShared(bool S) { Shared = S; } | |||
200 | ||||
201 | void destroy() { | |||
202 | if (StackBase == nullptr) | |||
203 | return; | |||
204 | __munmap(StackBase, MaxSize); | |||
205 | } | |||
206 | ||||
207 | private: | |||
208 | static constexpr uint64_t Magic = 0x1122334455667788ull; | |||
209 | uint64_t MaxSize = 0xa00000; | |||
210 | uint8_t *StackBase{nullptr}; | |||
211 | uint64_t StackSize{0}; | |||
212 | bool Shared{false}; | |||
213 | Mutex M; | |||
214 | }; | |||
215 | ||||
216 | /// Used for allocating indirect call instrumentation counters. Initialized by | |||
217 | /// __bolt_instr_setup, our initialization routine. | |||
218 | BumpPtrAllocator GlobalAlloc; | |||
219 | } // anonymous namespace | |||
220 | ||||
221 | // User-defined placement new operators. We only use those (as opposed to | |||
222 | // overriding the regular operator new) so we can keep our allocator in the | |||
223 | // stack instead of in a data section (global). | |||
224 | void *operator new(size_t Sz, BumpPtrAllocator &A) { return A.allocate(Sz); } | |||
225 | void *operator new(size_t Sz, BumpPtrAllocator &A, char C) { | |||
226 | auto *Ptr = reinterpret_cast<char *>(A.allocate(Sz)); | |||
227 | memset(Ptr, C, Sz); | |||
228 | return Ptr; | |||
229 | } | |||
230 | void *operator new[](size_t Sz, BumpPtrAllocator &A) { | |||
231 | return A.allocate(Sz); | |||
232 | } | |||
233 | void *operator new[](size_t Sz, BumpPtrAllocator &A, char C) { | |||
234 | auto *Ptr = reinterpret_cast<char *>(A.allocate(Sz)); | |||
235 | memset(Ptr, C, Sz); | |||
236 | return Ptr; | |||
237 | } | |||
238 | // Only called during exception unwinding (useless). We must manually dealloc. | |||
239 | // C++ language weirdness | |||
240 | void operator delete(void *Ptr, BumpPtrAllocator &A) { A.deallocate(Ptr); } | |||
241 | ||||
242 | namespace { | |||
243 | ||||
244 | // Disable instrumentation optimizations that sacrifice profile accuracy | |||
245 | extern "C" bool __bolt_instr_conservative; | |||
246 | ||||
247 | /// Basic key-val atom stored in our hash | |||
248 | struct SimpleHashTableEntryBase { | |||
249 | uint64_t Key; | |||
250 | uint64_t Val; | |||
251 | }; | |||
252 | ||||
253 | /// This hash table implementation starts by allocating a table of size | |||
254 | /// InitialSize. When conflicts happen in this main table, it resolves | |||
255 | /// them by chaining a new table of size IncSize. It never reallocs as our | |||
256 | /// allocator doesn't support it. The key is intended to be function pointers. | |||
257 | /// There's no clever hash function (it's just x mod size, size being prime). | |||
258 | /// I never tuned the coefficientes in the modular equation (TODO) | |||
259 | /// This is used for indirect calls (each call site has one of this, so it | |||
260 | /// should have a small footprint) and for tallying call counts globally for | |||
261 | /// each target to check if we missed the origin of some calls (this one is a | |||
262 | /// large instantiation of this template, since it is global for all call sites) | |||
263 | template <typename T = SimpleHashTableEntryBase, uint32_t InitialSize = 7, | |||
264 | uint32_t IncSize = 7> | |||
265 | class SimpleHashTable { | |||
266 | public: | |||
267 | using MapEntry = T; | |||
268 | ||||
269 | /// Increment by 1 the value of \p Key. If it is not in this table, it will be | |||
270 | /// added to the table and its value set to 1. | |||
271 | void incrementVal(uint64_t Key, BumpPtrAllocator &Alloc) { | |||
272 | ++get(Key, Alloc).Val; | |||
273 | } | |||
274 | ||||
275 | /// Basic member accessing interface. Here we pass the allocator explicitly to | |||
276 | /// avoid storing a pointer to it as part of this table (remember there is one | |||
277 | /// hash for each indirect call site, so we wan't to minimize our footprint). | |||
278 | MapEntry &get(uint64_t Key, BumpPtrAllocator &Alloc) { | |||
279 | if (!__bolt_instr_conservative) { | |||
280 | TryLock L(M); | |||
281 | if (!L.isLocked()) | |||
282 | return NoEntry; | |||
283 | return getOrAllocEntry(Key, Alloc); | |||
284 | } | |||
285 | Lock L(M); | |||
286 | return getOrAllocEntry(Key, Alloc); | |||
287 | } | |||
288 | ||||
289 | /// Traverses all elements in the table | |||
290 | template <typename... Args> | |||
291 | void forEachElement(void (*Callback)(MapEntry &, Args...), Args... args) { | |||
292 | Lock L(M); | |||
293 | if (!TableRoot) | |||
294 | return; | |||
295 | return forEachElement(Callback, InitialSize, TableRoot, args...); | |||
296 | } | |||
297 | ||||
298 | void resetCounters(); | |||
299 | ||||
300 | private: | |||
301 | constexpr static uint64_t VacantMarker = 0; | |||
302 | constexpr static uint64_t FollowUpTableMarker = 0x8000000000000000ull; | |||
303 | ||||
304 | MapEntry *TableRoot{nullptr}; | |||
305 | MapEntry NoEntry; | |||
306 | Mutex M; | |||
307 | ||||
308 | template <typename... Args> | |||
309 | void forEachElement(void (*Callback)(MapEntry &, Args...), | |||
310 | uint32_t NumEntries, MapEntry *Entries, Args... args) { | |||
311 | for (uint32_t I = 0; I < NumEntries; ++I) { | |||
312 | MapEntry &Entry = Entries[I]; | |||
313 | if (Entry.Key == VacantMarker) | |||
314 | continue; | |||
315 | if (Entry.Key & FollowUpTableMarker) { | |||
316 | forEachElement(Callback, IncSize, | |||
317 | reinterpret_cast<MapEntry *>(Entry.Key & | |||
318 | ~FollowUpTableMarker), | |||
319 | args...); | |||
320 | continue; | |||
321 | } | |||
322 | Callback(Entry, args...); | |||
323 | } | |||
324 | } | |||
325 | ||||
326 | MapEntry &firstAllocation(uint64_t Key, BumpPtrAllocator &Alloc) { | |||
327 | TableRoot = new (Alloc, 0) MapEntry[InitialSize]; | |||
328 | MapEntry &Entry = TableRoot[Key % InitialSize]; | |||
329 | Entry.Key = Key; | |||
330 | return Entry; | |||
331 | } | |||
332 | ||||
333 | MapEntry &getEntry(MapEntry *Entries, uint64_t Key, uint64_t Selector, | |||
334 | BumpPtrAllocator &Alloc, int CurLevel) { | |||
335 | const uint32_t NumEntries = CurLevel == 0 ? InitialSize : IncSize; | |||
336 | uint64_t Remainder = Selector / NumEntries; | |||
337 | Selector = Selector % NumEntries; | |||
338 | MapEntry &Entry = Entries[Selector]; | |||
339 | ||||
340 | // A hit | |||
341 | if (Entry.Key == Key) { | |||
342 | return Entry; | |||
343 | } | |||
344 | ||||
345 | // Vacant - add new entry | |||
346 | if (Entry.Key == VacantMarker) { | |||
347 | Entry.Key = Key; | |||
348 | return Entry; | |||
349 | } | |||
350 | ||||
351 | // Defer to the next level | |||
352 | if (Entry.Key & FollowUpTableMarker) { | |||
353 | return getEntry( | |||
354 | reinterpret_cast<MapEntry *>(Entry.Key & ~FollowUpTableMarker), | |||
355 | Key, Remainder, Alloc, CurLevel + 1); | |||
356 | } | |||
357 | ||||
358 | // Conflict - create the next level | |||
359 | MapEntry *NextLevelTbl = new (Alloc, 0) MapEntry[IncSize]; | |||
360 | uint64_t CurEntrySelector = Entry.Key / InitialSize; | |||
361 | for (int I = 0; I < CurLevel; ++I) | |||
362 | CurEntrySelector /= IncSize; | |||
363 | CurEntrySelector = CurEntrySelector % IncSize; | |||
364 | NextLevelTbl[CurEntrySelector] = Entry; | |||
365 | Entry.Key = reinterpret_cast<uint64_t>(NextLevelTbl) | FollowUpTableMarker; | |||
366 | return getEntry(NextLevelTbl, Key, Remainder, Alloc, CurLevel + 1); | |||
367 | } | |||
368 | ||||
369 | MapEntry &getOrAllocEntry(uint64_t Key, BumpPtrAllocator &Alloc) { | |||
370 | if (TableRoot) | |||
371 | return getEntry(TableRoot, Key, Key, Alloc, 0); | |||
372 | return firstAllocation(Key, Alloc); | |||
373 | } | |||
374 | }; | |||
375 | ||||
376 | template <typename T> void resetIndCallCounter(T &Entry) { | |||
377 | Entry.Val = 0; | |||
378 | } | |||
379 | ||||
380 | template <typename T, uint32_t X, uint32_t Y> | |||
381 | void SimpleHashTable<T, X, Y>::resetCounters() { | |||
382 | forEachElement(resetIndCallCounter); | |||
383 | } | |||
384 | ||||
385 | /// Represents a hash table mapping a function target address to its counter. | |||
386 | using IndirectCallHashTable = SimpleHashTable<>; | |||
387 | ||||
388 | /// Initialize with number 1 instead of 0 so we don't go into .bss. This is the | |||
389 | /// global array of all hash tables storing indirect call destinations happening | |||
390 | /// during runtime, one table per call site. | |||
391 | IndirectCallHashTable *GlobalIndCallCounters{ | |||
392 | reinterpret_cast<IndirectCallHashTable *>(1)}; | |||
393 | ||||
394 | /// Don't allow reentrancy in the fdata writing phase - only one thread writes | |||
395 | /// it | |||
396 | Mutex *GlobalWriteProfileMutex{reinterpret_cast<Mutex *>(1)}; | |||
397 | ||||
398 | /// Store number of calls in additional to target address (Key) and frequency | |||
399 | /// as perceived by the basic block counter (Val). | |||
400 | struct CallFlowEntryBase : public SimpleHashTableEntryBase { | |||
401 | uint64_t Calls; | |||
402 | }; | |||
403 | ||||
404 | using CallFlowHashTableBase = SimpleHashTable<CallFlowEntryBase, 11939, 233>; | |||
405 | ||||
406 | /// This is a large table indexing all possible call targets (indirect and | |||
407 | /// direct ones). The goal is to find mismatches between number of calls (for | |||
408 | /// those calls we were able to track) and the entry basic block counter of the | |||
409 | /// callee. In most cases, these two should be equal. If not, there are two | |||
410 | /// possible scenarios here: | |||
411 | /// | |||
412 | /// * Entry BB has higher frequency than all known calls to this function. | |||
413 | /// In this case, we have dynamic library code or any uninstrumented code | |||
414 | /// calling this function. We will write the profile for these untracked | |||
415 | /// calls as having source "0 [unknown] 0" in the fdata file. | |||
416 | /// | |||
417 | /// * Number of known calls is higher than the frequency of entry BB | |||
418 | /// This only happens when there is no counter for the entry BB / callee | |||
419 | /// function is not simple (in BOLT terms). We don't do anything special | |||
420 | /// here and just ignore those (we still report all calls to the non-simple | |||
421 | /// function, though). | |||
422 | /// | |||
423 | class CallFlowHashTable : public CallFlowHashTableBase { | |||
424 | public: | |||
425 | CallFlowHashTable(BumpPtrAllocator &Alloc) : Alloc(Alloc) {} | |||
426 | ||||
427 | MapEntry &get(uint64_t Key) { return CallFlowHashTableBase::get(Key, Alloc); } | |||
428 | ||||
429 | private: | |||
430 | // Different than the hash table for indirect call targets, we do store the | |||
431 | // allocator here since there is only one call flow hash and space overhead | |||
432 | // is negligible. | |||
433 | BumpPtrAllocator &Alloc; | |||
434 | }; | |||
435 | ||||
436 | /// | |||
437 | /// Description metadata emitted by BOLT to describe the program - refer to | |||
438 | /// Passes/Instrumentation.cpp - Instrumentation::emitTablesAsELFNote() | |||
439 | /// | |||
440 | struct Location { | |||
441 | uint32_t FunctionName; | |||
442 | uint32_t Offset; | |||
443 | }; | |||
444 | ||||
445 | struct CallDescription { | |||
446 | Location From; | |||
447 | uint32_t FromNode; | |||
448 | Location To; | |||
449 | uint32_t Counter; | |||
450 | uint64_t TargetAddress; | |||
451 | }; | |||
452 | ||||
453 | using IndCallDescription = Location; | |||
454 | ||||
455 | struct IndCallTargetDescription { | |||
456 | Location Loc; | |||
457 | uint64_t Address; | |||
458 | }; | |||
459 | ||||
460 | struct EdgeDescription { | |||
461 | Location From; | |||
462 | uint32_t FromNode; | |||
463 | Location To; | |||
464 | uint32_t ToNode; | |||
465 | uint32_t Counter; | |||
466 | }; | |||
467 | ||||
468 | struct InstrumentedNode { | |||
469 | uint32_t Node; | |||
470 | uint32_t Counter; | |||
471 | }; | |||
472 | ||||
473 | struct EntryNode { | |||
474 | uint64_t Node; | |||
475 | uint64_t Address; | |||
476 | }; | |||
477 | ||||
478 | struct FunctionDescription { | |||
479 | uint32_t NumLeafNodes; | |||
480 | const InstrumentedNode *LeafNodes; | |||
481 | uint32_t NumEdges; | |||
482 | const EdgeDescription *Edges; | |||
483 | uint32_t NumCalls; | |||
484 | const CallDescription *Calls; | |||
485 | uint32_t NumEntryNodes; | |||
486 | const EntryNode *EntryNodes; | |||
487 | ||||
488 | /// Constructor will parse the serialized function metadata written by BOLT | |||
489 | FunctionDescription(const uint8_t *FuncDesc); | |||
490 | ||||
491 | uint64_t getSize() const { | |||
492 | return 16 + NumLeafNodes * sizeof(InstrumentedNode) + | |||
493 | NumEdges * sizeof(EdgeDescription) + | |||
494 | NumCalls * sizeof(CallDescription) + | |||
495 | NumEntryNodes * sizeof(EntryNode); | |||
496 | } | |||
497 | }; | |||
498 | ||||
499 | /// The context is created when the fdata profile needs to be written to disk | |||
500 | /// and we need to interpret our runtime counters. It contains pointers to the | |||
501 | /// mmaped binary (only the BOLT written metadata section). Deserialization | |||
502 | /// should be straightforward as most data is POD or an array of POD elements. | |||
503 | /// This metadata is used to reconstruct function CFGs. | |||
504 | struct ProfileWriterContext { | |||
505 | IndCallDescription *IndCallDescriptions; | |||
506 | IndCallTargetDescription *IndCallTargets; | |||
507 | uint8_t *FuncDescriptions; | |||
508 | char *Strings; // String table with function names used in this binary | |||
509 | int FileDesc; // File descriptor for the file on disk backing this | |||
510 | // information in memory via mmap | |||
511 | void *MMapPtr; // The mmap ptr | |||
512 | int MMapSize; // The mmap size | |||
513 | ||||
514 | /// Hash table storing all possible call destinations to detect untracked | |||
515 | /// calls and correctly report them as [unknown] in output fdata. | |||
516 | CallFlowHashTable *CallFlowTable; | |||
517 | ||||
518 | /// Lookup the sorted indirect call target vector to fetch function name and | |||
519 | /// offset for an arbitrary function pointer. | |||
520 | const IndCallTargetDescription *lookupIndCallTarget(uint64_t Target) const; | |||
521 | }; | |||
522 | ||||
523 | /// Perform a string comparison and returns zero if Str1 matches Str2. Compares | |||
524 | /// at most Size characters. | |||
525 | int compareStr(const char *Str1, const char *Str2, int Size) { | |||
526 | while (*Str1 == *Str2) { | |||
527 | if (*Str1 == '\0' || --Size == 0) | |||
528 | return 0; | |||
529 | ++Str1; | |||
530 | ++Str2; | |||
531 | } | |||
532 | return 1; | |||
533 | } | |||
534 | ||||
535 | /// Output Location to the fdata file | |||
536 | char *serializeLoc(const ProfileWriterContext &Ctx, char *OutBuf, | |||
537 | const Location Loc, uint32_t BufSize) { | |||
538 | // fdata location format: Type Name Offset | |||
539 | // Type 1 - regular symbol | |||
540 | OutBuf = strCopy(OutBuf, "1 "); | |||
541 | const char *Str = Ctx.Strings + Loc.FunctionName; | |||
542 | uint32_t Size = 25; | |||
543 | while (*Str) { | |||
544 | *OutBuf++ = *Str++; | |||
545 | if (++Size >= BufSize) | |||
546 | break; | |||
547 | } | |||
548 | assert(!*Str, "buffer overflow, function name too large"); | |||
549 | *OutBuf++ = ' '; | |||
550 | OutBuf = intToStr(OutBuf, Loc.Offset, 16); | |||
551 | *OutBuf++ = ' '; | |||
552 | return OutBuf; | |||
553 | } | |||
554 | ||||
555 | /// Read and deserialize a function description written by BOLT. \p FuncDesc | |||
556 | /// points at the beginning of the function metadata structure in the file. | |||
557 | /// See Instrumentation::emitTablesAsELFNote() | |||
558 | FunctionDescription::FunctionDescription(const uint8_t *FuncDesc) { | |||
559 | NumLeafNodes = *reinterpret_cast<const uint32_t *>(FuncDesc); | |||
560 | DEBUG(reportNumber("NumLeafNodes = ", NumLeafNodes, 10)){}; | |||
561 | LeafNodes = reinterpret_cast<const InstrumentedNode *>(FuncDesc + 4); | |||
562 | ||||
563 | NumEdges = *reinterpret_cast<const uint32_t *>( | |||
564 | FuncDesc + 4 + NumLeafNodes * sizeof(InstrumentedNode)); | |||
565 | DEBUG(reportNumber("NumEdges = ", NumEdges, 10)){}; | |||
566 | Edges = reinterpret_cast<const EdgeDescription *>( | |||
567 | FuncDesc + 8 + NumLeafNodes * sizeof(InstrumentedNode)); | |||
568 | ||||
569 | NumCalls = *reinterpret_cast<const uint32_t *>( | |||
570 | FuncDesc + 8 + NumLeafNodes * sizeof(InstrumentedNode) + | |||
571 | NumEdges * sizeof(EdgeDescription)); | |||
572 | DEBUG(reportNumber("NumCalls = ", NumCalls, 10)){}; | |||
573 | Calls = reinterpret_cast<const CallDescription *>( | |||
574 | FuncDesc + 12 + NumLeafNodes * sizeof(InstrumentedNode) + | |||
575 | NumEdges * sizeof(EdgeDescription)); | |||
576 | NumEntryNodes = *reinterpret_cast<const uint32_t *>( | |||
577 | FuncDesc + 12 + NumLeafNodes * sizeof(InstrumentedNode) + | |||
578 | NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription)); | |||
579 | DEBUG(reportNumber("NumEntryNodes = ", NumEntryNodes, 10)){}; | |||
580 | EntryNodes = reinterpret_cast<const EntryNode *>( | |||
581 | FuncDesc + 16 + NumLeafNodes * sizeof(InstrumentedNode) + | |||
582 | NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription)); | |||
583 | } | |||
584 | ||||
585 | /// Read and mmap descriptions written by BOLT from the executable's notes | |||
586 | /// section | |||
587 | #if defined(HAVE_ELF_H) and !defined(__APPLE__) | |||
588 | ||||
589 | void *__attribute__((noinline)) __get_pc() { | |||
590 | return __builtin_extract_return_addr(__builtin_return_address(0)); | |||
591 | } | |||
592 | ||||
593 | /// Get string with address and parse it to hex pair <StartAddress, EndAddress> | |||
594 | bool parseAddressRange(const char *Str, uint64_t &StartAddress, | |||
595 | uint64_t &EndAddress) { | |||
596 | if (!Str) | |||
597 | return false; | |||
598 | // Parsed string format: <hex1>-<hex2> | |||
599 | StartAddress = hexToLong(Str, '-'); | |||
600 | while (*Str && *Str != '-') | |||
601 | ++Str; | |||
602 | if (!*Str) | |||
603 | return false; | |||
604 | ++Str; // swallow '-' | |||
605 | EndAddress = hexToLong(Str); | |||
606 | return true; | |||
607 | } | |||
608 | ||||
609 | /// Get full path to the real binary by getting current virtual address | |||
610 | /// and searching for the appropriate link in address range in | |||
611 | /// /proc/self/map_files | |||
612 | static char *getBinaryPath() { | |||
613 | const uint32_t BufSize = 1024; | |||
614 | const uint32_t NameMax = 4096; | |||
615 | const char DirPath[] = "/proc/self/map_files/"; | |||
616 | static char TargetPath[NameMax] = {}; | |||
617 | char Buf[BufSize]; | |||
618 | ||||
619 | if (__bolt_instr_binpath[0] != '\0') | |||
620 | return __bolt_instr_binpath; | |||
621 | ||||
622 | if (TargetPath[0] != '\0') | |||
623 | return TargetPath; | |||
624 | ||||
625 | unsigned long CurAddr = (unsigned long)__get_pc(); | |||
626 | uint64_t FDdir = __open(DirPath, | |||
627 | /*flags=*/0 /*O_RDONLY*/, | |||
628 | /*mode=*/0666); | |||
629 | assert(static_cast<int64_t>(FDdir) >= 0, | |||
630 | "failed to open /proc/self/map_files"); | |||
631 | ||||
632 | while (long Nread = __getdents(FDdir, (struct dirent *)Buf, BufSize)) { | |||
633 | assert(static_cast<int64_t>(Nread) != -1, "failed to get folder entries"); | |||
634 | ||||
635 | struct dirent *d; | |||
636 | for (long Bpos = 0; Bpos < Nread; Bpos += d->d_reclen) { | |||
637 | d = (struct dirent *)(Buf + Bpos); | |||
638 | ||||
639 | uint64_t StartAddress, EndAddress; | |||
640 | if (!parseAddressRange(d->d_name, StartAddress, EndAddress)) | |||
641 | continue; | |||
642 | if (CurAddr < StartAddress || CurAddr > EndAddress) | |||
643 | continue; | |||
644 | char FindBuf[NameMax]; | |||
645 | char *C = strCopy(FindBuf, DirPath, NameMax); | |||
646 | C = strCopy(C, d->d_name, NameMax - (C - FindBuf)); | |||
647 | *C = '\0'; | |||
648 | uint32_t Ret = __readlink(FindBuf, TargetPath, sizeof(TargetPath)); | |||
649 | assert(Ret != -1 && Ret != BufSize, "readlink error"); | |||
650 | TargetPath[Ret] = '\0'; | |||
651 | return TargetPath; | |||
652 | } | |||
653 | } | |||
654 | return nullptr; | |||
655 | } | |||
656 | ||||
657 | ProfileWriterContext readDescriptions() { | |||
658 | ProfileWriterContext Result; | |||
659 | char *BinPath = getBinaryPath(); | |||
660 | assert(BinPath && BinPath[0] != '\0', "failed to find binary path"); | |||
661 | ||||
662 | uint64_t FD = __open(BinPath, | |||
663 | /*flags=*/0 /*O_RDONLY*/, | |||
664 | /*mode=*/0666); | |||
665 | assert(static_cast<int64_t>(FD) >= 0, "failed to open binary path"); | |||
666 | ||||
667 | Result.FileDesc = FD; | |||
668 | ||||
669 | // mmap our binary to memory | |||
670 | uint64_t Size = __lseek(FD, 0, 2 /*SEEK_END*/); | |||
671 | uint8_t *BinContents = reinterpret_cast<uint8_t *>( | |||
672 | __mmap(0, Size, 0x1 /* PROT_READ*/, 0x2 /* MAP_PRIVATE*/, FD, 0)); | |||
673 | Result.MMapPtr = BinContents; | |||
674 | Result.MMapSize = Size; | |||
675 | Elf64_Ehdr *Hdr = reinterpret_cast<Elf64_Ehdr *>(BinContents); | |||
676 | Elf64_Shdr *Shdr = reinterpret_cast<Elf64_Shdr *>(BinContents + Hdr->e_shoff); | |||
677 | Elf64_Shdr *StringTblHeader = reinterpret_cast<Elf64_Shdr *>( | |||
678 | BinContents + Hdr->e_shoff + Hdr->e_shstrndx * Hdr->e_shentsize); | |||
679 | ||||
680 | // Find .bolt.instr.tables with the data we need and set pointers to it | |||
681 | for (int I = 0; I < Hdr->e_shnum; ++I) { | |||
682 | char *SecName = reinterpret_cast<char *>( | |||
683 | BinContents + StringTblHeader->sh_offset + Shdr->sh_name); | |||
684 | if (compareStr(SecName, ".bolt.instr.tables", 64) != 0) { | |||
685 | Shdr = reinterpret_cast<Elf64_Shdr *>(BinContents + Hdr->e_shoff + | |||
686 | (I + 1) * Hdr->e_shentsize); | |||
687 | continue; | |||
688 | } | |||
689 | // Actual contents of the ELF note start after offset 20 decimal: | |||
690 | // Offset 0: Producer name size (4 bytes) | |||
691 | // Offset 4: Contents size (4 bytes) | |||
692 | // Offset 8: Note type (4 bytes) | |||
693 | // Offset 12: Producer name (BOLT\0) (5 bytes + align to 4-byte boundary) | |||
694 | // Offset 20: Contents | |||
695 | uint32_t IndCallDescSize = | |||
696 | *reinterpret_cast<uint32_t *>(BinContents + Shdr->sh_offset + 20); | |||
697 | uint32_t IndCallTargetDescSize = *reinterpret_cast<uint32_t *>( | |||
698 | BinContents + Shdr->sh_offset + 24 + IndCallDescSize); | |||
699 | uint32_t FuncDescSize = | |||
700 | *reinterpret_cast<uint32_t *>(BinContents + Shdr->sh_offset + 28 + | |||
701 | IndCallDescSize + IndCallTargetDescSize); | |||
702 | Result.IndCallDescriptions = reinterpret_cast<IndCallDescription *>( | |||
703 | BinContents + Shdr->sh_offset + 24); | |||
704 | Result.IndCallTargets = reinterpret_cast<IndCallTargetDescription *>( | |||
705 | BinContents + Shdr->sh_offset + 28 + IndCallDescSize); | |||
706 | Result.FuncDescriptions = BinContents + Shdr->sh_offset + 32 + | |||
707 | IndCallDescSize + IndCallTargetDescSize; | |||
708 | Result.Strings = reinterpret_cast<char *>( | |||
709 | BinContents + Shdr->sh_offset + 32 + IndCallDescSize + | |||
710 | IndCallTargetDescSize + FuncDescSize); | |||
711 | return Result; | |||
712 | } | |||
713 | const char ErrMsg[] = | |||
714 | "BOLT instrumentation runtime error: could not find section " | |||
715 | ".bolt.instr.tables\n"; | |||
716 | reportError(ErrMsg, sizeof(ErrMsg)); | |||
717 | return Result; | |||
718 | } | |||
719 | ||||
720 | #else | |||
721 | ||||
722 | ProfileWriterContext readDescriptions() { | |||
723 | ProfileWriterContext Result; | |||
724 | uint8_t *Tables = _bolt_instr_tables_getter(); | |||
725 | uint32_t IndCallDescSize = *reinterpret_cast<uint32_t *>(Tables); | |||
726 | uint32_t IndCallTargetDescSize = | |||
727 | *reinterpret_cast<uint32_t *>(Tables + 4 + IndCallDescSize); | |||
728 | uint32_t FuncDescSize = *reinterpret_cast<uint32_t *>( | |||
729 | Tables + 8 + IndCallDescSize + IndCallTargetDescSize); | |||
730 | Result.IndCallDescriptions = | |||
731 | reinterpret_cast<IndCallDescription *>(Tables + 4); | |||
732 | Result.IndCallTargets = reinterpret_cast<IndCallTargetDescription *>( | |||
733 | Tables + 8 + IndCallDescSize); | |||
734 | Result.FuncDescriptions = | |||
735 | Tables + 12 + IndCallDescSize + IndCallTargetDescSize; | |||
736 | Result.Strings = reinterpret_cast<char *>( | |||
737 | Tables + 12 + IndCallDescSize + IndCallTargetDescSize + FuncDescSize); | |||
738 | return Result; | |||
739 | } | |||
740 | ||||
741 | #endif | |||
742 | ||||
743 | #if !defined(__APPLE__) | |||
744 | /// Debug by printing overall metadata global numbers to check it is sane | |||
745 | void printStats(const ProfileWriterContext &Ctx) { | |||
746 | char StatMsg[BufSize]; | |||
747 | char *StatPtr = StatMsg; | |||
748 | StatPtr = | |||
749 | strCopy(StatPtr, | |||
750 | "\nBOLT INSTRUMENTATION RUNTIME STATISTICS\n\nIndCallDescSize: "); | |||
751 | StatPtr = intToStr(StatPtr, | |||
752 | Ctx.FuncDescriptions - | |||
753 | reinterpret_cast<uint8_t *>(Ctx.IndCallDescriptions), | |||
754 | 10); | |||
755 | StatPtr = strCopy(StatPtr, "\nFuncDescSize: "); | |||
756 | StatPtr = intToStr( | |||
757 | StatPtr, | |||
758 | reinterpret_cast<uint8_t *>(Ctx.Strings) - Ctx.FuncDescriptions, 10); | |||
759 | StatPtr = strCopy(StatPtr, "\n__bolt_instr_num_ind_calls: "); | |||
760 | StatPtr = intToStr(StatPtr, __bolt_instr_num_ind_calls, 10); | |||
761 | StatPtr = strCopy(StatPtr, "\n__bolt_instr_num_funcs: "); | |||
762 | StatPtr = intToStr(StatPtr, __bolt_instr_num_funcs, 10); | |||
763 | StatPtr = strCopy(StatPtr, "\n"); | |||
764 | __write(2, StatMsg, StatPtr - StatMsg); | |||
765 | } | |||
766 | #endif | |||
767 | ||||
768 | ||||
769 | /// This is part of a simple CFG representation in memory, where we store | |||
770 | /// a dynamically sized array of input and output edges per node, and store | |||
771 | /// a dynamically sized array of nodes per graph. We also store the spanning | |||
772 | /// tree edges for that CFG in a separate array of nodes in | |||
773 | /// \p SpanningTreeNodes, while the regular nodes live in \p CFGNodes. | |||
774 | struct Edge { | |||
775 | uint32_t Node; // Index in nodes array regarding the destination of this edge | |||
776 | uint32_t ID; // Edge index in an array comprising all edges of the graph | |||
777 | }; | |||
778 | ||||
779 | /// A regular graph node or a spanning tree node | |||
780 | struct Node { | |||
781 | uint32_t NumInEdges{0}; // Input edge count used to size InEdge | |||
782 | uint32_t NumOutEdges{0}; // Output edge count used to size OutEdges | |||
783 | Edge *InEdges{nullptr}; // Created and managed by \p Graph | |||
784 | Edge *OutEdges{nullptr}; // ditto | |||
785 | }; | |||
786 | ||||
787 | /// Main class for CFG representation in memory. Manages object creation and | |||
788 | /// destruction, populates an array of CFG nodes as well as corresponding | |||
789 | /// spanning tree nodes. | |||
790 | struct Graph { | |||
791 | uint32_t NumNodes; | |||
792 | Node *CFGNodes; | |||
793 | Node *SpanningTreeNodes; | |||
794 | uint64_t *EdgeFreqs; | |||
795 | uint64_t *CallFreqs; | |||
796 | BumpPtrAllocator &Alloc; | |||
797 | const FunctionDescription &D; | |||
798 | ||||
799 | /// Reads a list of edges from function description \p D and builds | |||
800 | /// the graph from it. Allocates several internal dynamic structures that are | |||
801 | /// later destroyed by ~Graph() and uses \p Alloc. D.LeafNodes contain all | |||
802 | /// spanning tree leaf nodes descriptions (their counters). They are the seed | |||
803 | /// used to compute the rest of the missing edge counts in a bottom-up | |||
804 | /// traversal of the spanning tree. | |||
805 | Graph(BumpPtrAllocator &Alloc, const FunctionDescription &D, | |||
806 | const uint64_t *Counters, ProfileWriterContext &Ctx); | |||
807 | ~Graph(); | |||
808 | void dump() const; | |||
809 | ||||
810 | private: | |||
811 | void computeEdgeFrequencies(const uint64_t *Counters, | |||
812 | ProfileWriterContext &Ctx); | |||
813 | void dumpEdgeFreqs() const; | |||
814 | }; | |||
815 | ||||
816 | Graph::Graph(BumpPtrAllocator &Alloc, const FunctionDescription &D, | |||
817 | const uint64_t *Counters, ProfileWriterContext &Ctx) | |||
818 | : Alloc(Alloc), D(D) { | |||
819 | DEBUG(reportNumber("G = 0x", (uint64_t)this, 16)){}; | |||
820 | // First pass to determine number of nodes | |||
821 | int32_t MaxNodes = -1; | |||
822 | CallFreqs = nullptr; | |||
823 | EdgeFreqs = nullptr; | |||
824 | for (int I = 0; I < D.NumEdges; ++I) { | |||
825 | if (static_cast<int32_t>(D.Edges[I].FromNode) > MaxNodes) | |||
826 | MaxNodes = D.Edges[I].FromNode; | |||
827 | if (static_cast<int32_t>(D.Edges[I].ToNode) > MaxNodes) | |||
828 | MaxNodes = D.Edges[I].ToNode; | |||
829 | } | |||
830 | ||||
831 | for (int I = 0; I < D.NumLeafNodes; ++I) | |||
832 | if (static_cast<int32_t>(D.LeafNodes[I].Node) > MaxNodes) | |||
833 | MaxNodes = D.LeafNodes[I].Node; | |||
834 | ||||
835 | for (int I = 0; I < D.NumCalls; ++I) | |||
836 | if (static_cast<int32_t>(D.Calls[I].FromNode) > MaxNodes) | |||
837 | MaxNodes = D.Calls[I].FromNode; | |||
838 | ||||
839 | // No nodes? Nothing to do | |||
840 | if (MaxNodes < 0) { | |||
841 | DEBUG(report("No nodes!\n")){}; | |||
842 | CFGNodes = nullptr; | |||
843 | SpanningTreeNodes = nullptr; | |||
844 | NumNodes = 0; | |||
845 | return; | |||
846 | } | |||
847 | ++MaxNodes; | |||
848 | DEBUG(reportNumber("NumNodes = ", MaxNodes, 10)){}; | |||
849 | NumNodes = static_cast<uint32_t>(MaxNodes); | |||
850 | ||||
851 | // Initial allocations | |||
852 | CFGNodes = new (Alloc) Node[MaxNodes]; | |||
853 | ||||
854 | DEBUG(reportNumber("G->CFGNodes = 0x", (uint64_t)CFGNodes, 16)){}; | |||
855 | SpanningTreeNodes = new (Alloc) Node[MaxNodes]; | |||
856 | DEBUG(reportNumber("G->SpanningTreeNodes = 0x",{} | |||
857 | (uint64_t)SpanningTreeNodes, 16)){}; | |||
858 | ||||
859 | // Figure out how much to allocate to each vector (in/out edge sets) | |||
860 | for (int I = 0; I < D.NumEdges; ++I) { | |||
861 | CFGNodes[D.Edges[I].FromNode].NumOutEdges++; | |||
862 | CFGNodes[D.Edges[I].ToNode].NumInEdges++; | |||
863 | if (D.Edges[I].Counter != 0xffffffff) | |||
864 | continue; | |||
865 | ||||
866 | SpanningTreeNodes[D.Edges[I].FromNode].NumOutEdges++; | |||
867 | SpanningTreeNodes[D.Edges[I].ToNode].NumInEdges++; | |||
868 | } | |||
869 | ||||
870 | // Allocate in/out edge sets | |||
871 | for (int I = 0; I < MaxNodes; ++I) { | |||
872 | if (CFGNodes[I].NumInEdges > 0) | |||
873 | CFGNodes[I].InEdges = new (Alloc) Edge[CFGNodes[I].NumInEdges]; | |||
874 | if (CFGNodes[I].NumOutEdges > 0) | |||
875 | CFGNodes[I].OutEdges = new (Alloc) Edge[CFGNodes[I].NumOutEdges]; | |||
876 | if (SpanningTreeNodes[I].NumInEdges > 0) | |||
877 | SpanningTreeNodes[I].InEdges = | |||
878 | new (Alloc) Edge[SpanningTreeNodes[I].NumInEdges]; | |||
879 | if (SpanningTreeNodes[I].NumOutEdges > 0) | |||
880 | SpanningTreeNodes[I].OutEdges = | |||
881 | new (Alloc) Edge[SpanningTreeNodes[I].NumOutEdges]; | |||
882 | CFGNodes[I].NumInEdges = 0; | |||
883 | CFGNodes[I].NumOutEdges = 0; | |||
884 | SpanningTreeNodes[I].NumInEdges = 0; | |||
885 | SpanningTreeNodes[I].NumOutEdges = 0; | |||
886 | } | |||
887 | ||||
888 | // Fill in/out edge sets | |||
889 | for (int I = 0; I < D.NumEdges; ++I) { | |||
890 | const uint32_t Src = D.Edges[I].FromNode; | |||
891 | const uint32_t Dst = D.Edges[I].ToNode; | |||
892 | Edge *E = &CFGNodes[Src].OutEdges[CFGNodes[Src].NumOutEdges++]; | |||
893 | E->Node = Dst; | |||
894 | E->ID = I; | |||
895 | ||||
896 | E = &CFGNodes[Dst].InEdges[CFGNodes[Dst].NumInEdges++]; | |||
897 | E->Node = Src; | |||
898 | E->ID = I; | |||
899 | ||||
900 | if (D.Edges[I].Counter != 0xffffffff) | |||
901 | continue; | |||
902 | ||||
903 | E = &SpanningTreeNodes[Src] | |||
904 | .OutEdges[SpanningTreeNodes[Src].NumOutEdges++]; | |||
905 | E->Node = Dst; | |||
906 | E->ID = I; | |||
907 | ||||
908 | E = &SpanningTreeNodes[Dst] | |||
909 | .InEdges[SpanningTreeNodes[Dst].NumInEdges++]; | |||
910 | E->Node = Src; | |||
911 | E->ID = I; | |||
912 | } | |||
913 | ||||
914 | computeEdgeFrequencies(Counters, Ctx); | |||
915 | } | |||
916 | ||||
917 | Graph::~Graph() { | |||
918 | if (CallFreqs) | |||
919 | Alloc.deallocate(CallFreqs); | |||
920 | if (EdgeFreqs) | |||
921 | Alloc.deallocate(EdgeFreqs); | |||
922 | for (int I = NumNodes - 1; I >= 0; --I) { | |||
923 | if (SpanningTreeNodes[I].OutEdges) | |||
924 | Alloc.deallocate(SpanningTreeNodes[I].OutEdges); | |||
925 | if (SpanningTreeNodes[I].InEdges) | |||
926 | Alloc.deallocate(SpanningTreeNodes[I].InEdges); | |||
927 | if (CFGNodes[I].OutEdges) | |||
928 | Alloc.deallocate(CFGNodes[I].OutEdges); | |||
929 | if (CFGNodes[I].InEdges) | |||
930 | Alloc.deallocate(CFGNodes[I].InEdges); | |||
931 | } | |||
932 | if (SpanningTreeNodes) | |||
933 | Alloc.deallocate(SpanningTreeNodes); | |||
934 | if (CFGNodes) | |||
935 | Alloc.deallocate(CFGNodes); | |||
936 | } | |||
937 | ||||
938 | void Graph::dump() const { | |||
939 | reportNumber("Dumping graph with number of nodes: ", NumNodes, 10); | |||
940 | report(" Full graph:\n"); | |||
941 | for (int I = 0; I < NumNodes; ++I) { | |||
942 | const Node *N = &CFGNodes[I]; | |||
943 | reportNumber(" Node #", I, 10); | |||
944 | reportNumber(" InEdges total ", N->NumInEdges, 10); | |||
945 | for (int J = 0; J < N->NumInEdges; ++J) | |||
946 | reportNumber(" ", N->InEdges[J].Node, 10); | |||
947 | reportNumber(" OutEdges total ", N->NumOutEdges, 10); | |||
948 | for (int J = 0; J < N->NumOutEdges; ++J) | |||
949 | reportNumber(" ", N->OutEdges[J].Node, 10); | |||
950 | report("\n"); | |||
951 | } | |||
952 | report(" Spanning tree:\n"); | |||
953 | for (int I = 0; I < NumNodes; ++I) { | |||
954 | const Node *N = &SpanningTreeNodes[I]; | |||
955 | reportNumber(" Node #", I, 10); | |||
956 | reportNumber(" InEdges total ", N->NumInEdges, 10); | |||
957 | for (int J = 0; J < N->NumInEdges; ++J) | |||
958 | reportNumber(" ", N->InEdges[J].Node, 10); | |||
959 | reportNumber(" OutEdges total ", N->NumOutEdges, 10); | |||
960 | for (int J = 0; J < N->NumOutEdges; ++J) | |||
961 | reportNumber(" ", N->OutEdges[J].Node, 10); | |||
962 | report("\n"); | |||
963 | } | |||
964 | } | |||
965 | ||||
966 | void Graph::dumpEdgeFreqs() const { | |||
967 | reportNumber( | |||
968 | "Dumping edge frequencies for graph with num edges: ", D.NumEdges, 10); | |||
969 | for (int I = 0; I < D.NumEdges; ++I) { | |||
970 | reportNumber("* Src: ", D.Edges[I].FromNode, 10); | |||
971 | reportNumber(" Dst: ", D.Edges[I].ToNode, 10); | |||
972 | reportNumber(" Cnt: ", EdgeFreqs[I], 10); | |||
973 | } | |||
974 | } | |||
975 | ||||
976 | /// Auxiliary map structure for fast lookups of which calls map to each node of | |||
977 | /// the function CFG | |||
978 | struct NodeToCallsMap { | |||
979 | struct MapEntry { | |||
980 | uint32_t NumCalls; | |||
981 | uint32_t *Calls; | |||
982 | }; | |||
983 | MapEntry *Entries; | |||
984 | BumpPtrAllocator &Alloc; | |||
985 | const uint32_t NumNodes; | |||
986 | ||||
987 | NodeToCallsMap(BumpPtrAllocator &Alloc, const FunctionDescription &D, | |||
988 | uint32_t NumNodes) | |||
989 | : Alloc(Alloc), NumNodes(NumNodes) { | |||
990 | Entries = new (Alloc, 0) MapEntry[NumNodes]; | |||
991 | for (int I = 0; I < D.NumCalls; ++I) { | |||
992 | DEBUG(reportNumber("Registering call in node ", D.Calls[I].FromNode, 10)){}; | |||
993 | ++Entries[D.Calls[I].FromNode].NumCalls; | |||
994 | } | |||
995 | for (int I = 0; I < NumNodes; ++I) { | |||
996 | Entries[I].Calls = Entries[I].NumCalls ? new (Alloc) | |||
997 | uint32_t[Entries[I].NumCalls] | |||
998 | : nullptr; | |||
999 | Entries[I].NumCalls = 0; | |||
1000 | } | |||
1001 | for (int I = 0; I < D.NumCalls; ++I) { | |||
1002 | MapEntry &Entry = Entries[D.Calls[I].FromNode]; | |||
1003 | Entry.Calls[Entry.NumCalls++] = I; | |||
1004 | } | |||
1005 | } | |||
1006 | ||||
1007 | /// Set the frequency of all calls in node \p NodeID to Freq. However, if | |||
1008 | /// the calls have their own counters and do not depend on the basic block | |||
1009 | /// counter, this means they have landing pads and throw exceptions. In this | |||
1010 | /// case, set their frequency with their counters and return the maximum | |||
1011 | /// value observed in such counters. This will be used as the new frequency | |||
1012 | /// at basic block entry. This is used to fix the CFG edge frequencies in the | |||
1013 | /// presence of exceptions. | |||
1014 | uint64_t visitAllCallsIn(uint32_t NodeID, uint64_t Freq, uint64_t *CallFreqs, | |||
1015 | const FunctionDescription &D, | |||
1016 | const uint64_t *Counters, | |||
1017 | ProfileWriterContext &Ctx) const { | |||
1018 | const MapEntry &Entry = Entries[NodeID]; | |||
1019 | uint64_t MaxValue = 0ull; | |||
1020 | for (int I = 0, E = Entry.NumCalls; I != E; ++I) { | |||
1021 | const uint32_t CallID = Entry.Calls[I]; | |||
1022 | DEBUG(reportNumber(" Setting freq for call ID: ", CallID, 10)){}; | |||
1023 | const CallDescription &CallDesc = D.Calls[CallID]; | |||
1024 | if (CallDesc.Counter == 0xffffffff) { | |||
1025 | CallFreqs[CallID] = Freq; | |||
1026 | DEBUG(reportNumber(" with : ", Freq, 10)){}; | |||
1027 | } else { | |||
1028 | const uint64_t CounterVal = Counters[CallDesc.Counter]; | |||
1029 | CallFreqs[CallID] = CounterVal; | |||
1030 | MaxValue = CounterVal > MaxValue ? CounterVal : MaxValue; | |||
1031 | DEBUG(reportNumber(" with (private counter) : ", CounterVal, 10)){}; | |||
1032 | } | |||
1033 | DEBUG(reportNumber(" Address: 0x", CallDesc.TargetAddress, 16)){}; | |||
1034 | if (CallFreqs[CallID] > 0) | |||
1035 | Ctx.CallFlowTable->get(CallDesc.TargetAddress).Calls += | |||
1036 | CallFreqs[CallID]; | |||
1037 | } | |||
1038 | return MaxValue; | |||
1039 | } | |||
1040 | ||||
1041 | ~NodeToCallsMap() { | |||
1042 | for (int I = NumNodes - 1; I >= 0; --I) | |||
1043 | if (Entries[I].Calls) | |||
1044 | Alloc.deallocate(Entries[I].Calls); | |||
1045 | Alloc.deallocate(Entries); | |||
1046 | } | |||
1047 | }; | |||
1048 | ||||
1049 | /// Fill an array with the frequency of each edge in the function represented | |||
1050 | /// by G, as well as another array for each call. | |||
1051 | void Graph::computeEdgeFrequencies(const uint64_t *Counters, | |||
1052 | ProfileWriterContext &Ctx) { | |||
1053 | if (NumNodes == 0) | |||
| ||||
1054 | return; | |||
1055 | ||||
1056 | EdgeFreqs = D.NumEdges ? new (Alloc, 0) uint64_t [D.NumEdges] : nullptr; | |||
1057 | CallFreqs = D.NumCalls ? new (Alloc, 0) uint64_t [D.NumCalls] : nullptr; | |||
1058 | ||||
1059 | // Setup a lookup for calls present in each node (BB) | |||
1060 | NodeToCallsMap *CallMap = new (Alloc) NodeToCallsMap(Alloc, D, NumNodes); | |||
1061 | ||||
1062 | // Perform a bottom-up, BFS traversal of the spanning tree in G. Edges in the | |||
1063 | // spanning tree don't have explicit counters. We must infer their value using | |||
1064 | // a linear combination of other counters (sum of counters of the outgoing | |||
1065 | // edges minus sum of counters of the incoming edges). | |||
1066 | uint32_t *Stack = new (Alloc) uint32_t [NumNodes]; | |||
1067 | uint32_t StackTop = 0; | |||
1068 | enum Status : uint8_t { S_NEW = 0, S_VISITING, S_VISITED }; | |||
1069 | Status *Visited = new (Alloc, 0) Status[NumNodes]; | |||
1070 | uint64_t *LeafFrequency = new (Alloc, 0) uint64_t[NumNodes]; | |||
1071 | uint64_t *EntryAddress = new (Alloc, 0) uint64_t[NumNodes]; | |||
1072 | ||||
1073 | // Setup a fast lookup for frequency of leaf nodes, which have special | |||
1074 | // basic block frequency instrumentation (they are not edge profiled). | |||
1075 | for (int I = 0; I < D.NumLeafNodes; ++I) { | |||
1076 | LeafFrequency[D.LeafNodes[I].Node] = Counters[D.LeafNodes[I].Counter]; | |||
1077 | DEBUG({{} | |||
1078 | if (Counters[D.LeafNodes[I].Counter] > 0) {{} | |||
1079 | reportNumber("Leaf Node# ", D.LeafNodes[I].Node, 10);{} | |||
1080 | reportNumber(" Counter: ", Counters[D.LeafNodes[I].Counter], 10);{} | |||
1081 | }{} | |||
1082 | }){}; | |||
1083 | } | |||
1084 | for (int I = 0; I < D.NumEntryNodes; ++I) { | |||
1085 | EntryAddress[D.EntryNodes[I].Node] = D.EntryNodes[I].Address; | |||
1086 | DEBUG({{} | |||
1087 | reportNumber("Entry Node# ", D.EntryNodes[I].Node, 10);{} | |||
1088 | reportNumber(" Address: ", D.EntryNodes[I].Address, 16);{} | |||
1089 | }){}; | |||
1090 | } | |||
1091 | // Add all root nodes to the stack | |||
1092 | for (int I = 0; I
| |||
1093 | if (SpanningTreeNodes[I].NumInEdges == 0) | |||
1094 | Stack[StackTop++] = I; | |||
1095 | ||||
1096 | // Empty stack? | |||
1097 | if (StackTop
| |||
1098 | DEBUG(report("Empty stack!\n")){}; | |||
1099 | Alloc.deallocate(EntryAddress); | |||
1100 | Alloc.deallocate(LeafFrequency); | |||
1101 | Alloc.deallocate(Visited); | |||
1102 | Alloc.deallocate(Stack); | |||
1103 | CallMap->~NodeToCallsMap(); | |||
1104 | Alloc.deallocate(CallMap); | |||
1105 | if (CallFreqs) | |||
1106 | Alloc.deallocate(CallFreqs); | |||
1107 | if (EdgeFreqs) | |||
1108 | Alloc.deallocate(EdgeFreqs); | |||
1109 | EdgeFreqs = nullptr; | |||
1110 | CallFreqs = nullptr; | |||
1111 | return; | |||
1112 | } | |||
1113 | // Add all known edge counts, will infer the rest | |||
1114 | for (int I = 0; I < D.NumEdges; ++I) { | |||
1115 | const uint32_t C = D.Edges[I].Counter; | |||
1116 | if (C == 0xffffffff) // inferred counter - we will compute its value | |||
1117 | continue; | |||
1118 | EdgeFreqs[I] = Counters[C]; | |||
1119 | } | |||
1120 | ||||
1121 | while (StackTop > 0) { | |||
1122 | const uint32_t Cur = Stack[--StackTop]; | |||
1123 | DEBUG({{} | |||
1124 | if (Visited[Cur] == S_VISITING){} | |||
1125 | report("(visiting) ");{} | |||
1126 | else{} | |||
1127 | report("(new) ");{} | |||
1128 | reportNumber("Cur: ", Cur, 10);{} | |||
1129 | }){}; | |||
1130 | ||||
1131 | // This shouldn't happen in a tree | |||
1132 | assert(Visited[Cur] != S_VISITED, "should not have visited nodes in stack"); | |||
1133 | if (Visited[Cur] == S_NEW) { | |||
1134 | Visited[Cur] = S_VISITING; | |||
1135 | Stack[StackTop++] = Cur; | |||
1136 | assert(StackTop <= NumNodes, "stack grew too large"); | |||
1137 | for (int I = 0, E = SpanningTreeNodes[Cur].NumOutEdges; I < E; ++I) { | |||
1138 | const uint32_t Succ = SpanningTreeNodes[Cur].OutEdges[I].Node; | |||
1139 | Stack[StackTop++] = Succ; | |||
1140 | assert(StackTop <= NumNodes, "stack grew too large"); | |||
1141 | } | |||
1142 | continue; | |||
1143 | } | |||
1144 | Visited[Cur] = S_VISITED; | |||
1145 | ||||
1146 | // Establish our node frequency based on outgoing edges, which should all be | |||
1147 | // resolved by now. | |||
1148 | int64_t CurNodeFreq = LeafFrequency[Cur]; | |||
1149 | // Not a leaf? | |||
1150 | if (!CurNodeFreq) { | |||
1151 | for (int I = 0, E = CFGNodes[Cur].NumOutEdges; I != E; ++I) { | |||
1152 | const uint32_t SuccEdge = CFGNodes[Cur].OutEdges[I].ID; | |||
1153 | CurNodeFreq += EdgeFreqs[SuccEdge]; | |||
1154 | } | |||
1155 | } | |||
1156 | if (CurNodeFreq < 0) | |||
1157 | CurNodeFreq = 0; | |||
1158 | ||||
1159 | const uint64_t CallFreq = CallMap->visitAllCallsIn( | |||
1160 | Cur, CurNodeFreq
| |||
1161 | ||||
1162 | // Exception handling affected our output flow? Fix with calls info | |||
1163 | DEBUG({{} | |||
1164 | if (CallFreq > CurNodeFreq){} | |||
1165 | report("Bumping node frequency with call info\n");{} | |||
1166 | }){}; | |||
1167 | CurNodeFreq = CallFreq
| |||
1168 | ||||
1169 | if (CurNodeFreq
| |||
1170 | if (uint64_t Addr = EntryAddress[Cur]) { | |||
1171 | DEBUG({} | |||
1172 | reportNumber(" Setting flow at entry point address 0x", Addr, 16)){}; | |||
1173 | DEBUG(reportNumber(" with: ", CurNodeFreq, 10)){}; | |||
1174 | Ctx.CallFlowTable->get(Addr).Val = CurNodeFreq; | |||
1175 | } | |||
1176 | } | |||
1177 | ||||
1178 | // No parent? Reached a tree root, limit to call frequency updating. | |||
1179 | if (SpanningTreeNodes[Cur].NumInEdges == 0) | |||
1180 | continue; | |||
1181 | ||||
1182 | assert(SpanningTreeNodes[Cur].NumInEdges == 1, "must have 1 parent"); | |||
1183 | const uint32_t Parent = SpanningTreeNodes[Cur].InEdges[0].Node; | |||
1184 | const uint32_t ParentEdge = SpanningTreeNodes[Cur].InEdges[0].ID; | |||
1185 | ||||
1186 | // Calculate parent edge freq. | |||
1187 | int64_t ParentEdgeFreq = CurNodeFreq; | |||
1188 | for (int I = 0, E = CFGNodes[Cur].NumInEdges; I != E; ++I) { | |||
1189 | const uint32_t PredEdge = CFGNodes[Cur].InEdges[I].ID; | |||
1190 | ParentEdgeFreq -= EdgeFreqs[PredEdge]; | |||
| ||||
1191 | } | |||
1192 | ||||
1193 | // Sometimes the conservative CFG that BOLT builds will lead to incorrect | |||
1194 | // flow computation. For example, in a BB that transitively calls the exit | |||
1195 | // syscall, BOLT will add a fall-through successor even though it should not | |||
1196 | // have any successors. So this block execution will likely be wrong. We | |||
1197 | // tolerate this imperfection since this case should be quite infrequent. | |||
1198 | if (ParentEdgeFreq < 0) { | |||
1199 | DEBUG(dumpEdgeFreqs()){}; | |||
1200 | DEBUG(report("WARNING: incorrect flow")){}; | |||
1201 | ParentEdgeFreq = 0; | |||
1202 | } | |||
1203 | DEBUG(reportNumber(" Setting freq for ParentEdge: ", ParentEdge, 10)){}; | |||
1204 | DEBUG(reportNumber(" with ParentEdgeFreq: ", ParentEdgeFreq, 10)){}; | |||
1205 | EdgeFreqs[ParentEdge] = ParentEdgeFreq; | |||
1206 | } | |||
1207 | ||||
1208 | Alloc.deallocate(EntryAddress); | |||
1209 | Alloc.deallocate(LeafFrequency); | |||
1210 | Alloc.deallocate(Visited); | |||
1211 | Alloc.deallocate(Stack); | |||
1212 | CallMap->~NodeToCallsMap(); | |||
1213 | Alloc.deallocate(CallMap); | |||
1214 | DEBUG(dumpEdgeFreqs()){}; | |||
1215 | } | |||
1216 | ||||
1217 | /// Write to \p FD all of the edge profiles for function \p FuncDesc. Uses | |||
1218 | /// \p Alloc to allocate helper dynamic structures used to compute profile for | |||
1219 | /// edges that we do not explictly instrument. | |||
1220 | const uint8_t *writeFunctionProfile(int FD, ProfileWriterContext &Ctx, | |||
1221 | const uint8_t *FuncDesc, | |||
1222 | BumpPtrAllocator &Alloc) { | |||
1223 | const FunctionDescription F(FuncDesc); | |||
1224 | const uint8_t *next = FuncDesc + F.getSize(); | |||
1225 | ||||
1226 | #if !defined(__APPLE__) | |||
1227 | uint64_t *bolt_instr_locations = __bolt_instr_locations; | |||
1228 | #else | |||
1229 | uint64_t *bolt_instr_locations = _bolt_instr_locations_getter(); | |||
1230 | #endif | |||
1231 | ||||
1232 | // Skip funcs we know are cold | |||
1233 | #ifndef ENABLE_DEBUG | |||
1234 | uint64_t CountersFreq = 0; | |||
1235 | for (int I = 0; I < F.NumLeafNodes; ++I) | |||
1236 | CountersFreq += bolt_instr_locations[F.LeafNodes[I].Counter]; | |||
1237 | ||||
1238 | if (CountersFreq == 0) { | |||
1239 | for (int I = 0; I < F.NumEdges; ++I) { | |||
1240 | const uint32_t C = F.Edges[I].Counter; | |||
1241 | if (C == 0xffffffff) | |||
1242 | continue; | |||
1243 | CountersFreq += bolt_instr_locations[C]; | |||
1244 | } | |||
1245 | if (CountersFreq == 0) { | |||
1246 | for (int I = 0; I < F.NumCalls; ++I) { | |||
1247 | const uint32_t C = F.Calls[I].Counter; | |||
1248 | if (C == 0xffffffff) | |||
1249 | continue; | |||
1250 | CountersFreq += bolt_instr_locations[C]; | |||
1251 | } | |||
1252 | if (CountersFreq == 0) | |||
1253 | return next; | |||
1254 | } | |||
1255 | } | |||
1256 | #endif | |||
1257 | ||||
1258 | Graph *G = new (Alloc) Graph(Alloc, F, bolt_instr_locations, Ctx); | |||
1259 | DEBUG(G->dump()){}; | |||
1260 | ||||
1261 | if (!G->EdgeFreqs && !G->CallFreqs) { | |||
1262 | G->~Graph(); | |||
1263 | Alloc.deallocate(G); | |||
1264 | return next; | |||
1265 | } | |||
1266 | ||||
1267 | for (int I = 0; I < F.NumEdges; ++I) { | |||
1268 | const uint64_t Freq = G->EdgeFreqs[I]; | |||
1269 | if (Freq == 0) | |||
1270 | continue; | |||
1271 | const EdgeDescription *Desc = &F.Edges[I]; | |||
1272 | char LineBuf[BufSize]; | |||
1273 | char *Ptr = LineBuf; | |||
1274 | Ptr = serializeLoc(Ctx, Ptr, Desc->From, BufSize); | |||
1275 | Ptr = serializeLoc(Ctx, Ptr, Desc->To, BufSize - (Ptr - LineBuf)); | |||
1276 | Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 22); | |||
1277 | Ptr = intToStr(Ptr, Freq, 10); | |||
1278 | *Ptr++ = '\n'; | |||
1279 | __write(FD, LineBuf, Ptr - LineBuf); | |||
1280 | } | |||
1281 | ||||
1282 | for (int I = 0; I < F.NumCalls; ++I) { | |||
1283 | const uint64_t Freq = G->CallFreqs[I]; | |||
1284 | if (Freq == 0) | |||
1285 | continue; | |||
1286 | char LineBuf[BufSize]; | |||
1287 | char *Ptr = LineBuf; | |||
1288 | const CallDescription *Desc = &F.Calls[I]; | |||
1289 | Ptr = serializeLoc(Ctx, Ptr, Desc->From, BufSize); | |||
1290 | Ptr = serializeLoc(Ctx, Ptr, Desc->To, BufSize - (Ptr - LineBuf)); | |||
1291 | Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25); | |||
1292 | Ptr = intToStr(Ptr, Freq, 10); | |||
1293 | *Ptr++ = '\n'; | |||
1294 | __write(FD, LineBuf, Ptr - LineBuf); | |||
1295 | } | |||
1296 | ||||
1297 | G->~Graph(); | |||
1298 | Alloc.deallocate(G); | |||
1299 | return next; | |||
1300 | } | |||
1301 | ||||
1302 | #if !defined(__APPLE__) | |||
1303 | const IndCallTargetDescription * | |||
1304 | ProfileWriterContext::lookupIndCallTarget(uint64_t Target) const { | |||
1305 | uint32_t B = 0; | |||
1306 | uint32_t E = __bolt_instr_num_ind_targets; | |||
1307 | if (E == 0) | |||
1308 | return nullptr; | |||
1309 | do { | |||
1310 | uint32_t I = (E - B) / 2 + B; | |||
1311 | if (IndCallTargets[I].Address == Target) | |||
1312 | return &IndCallTargets[I]; | |||
1313 | if (IndCallTargets[I].Address < Target) | |||
1314 | B = I + 1; | |||
1315 | else | |||
1316 | E = I; | |||
1317 | } while (B < E); | |||
1318 | return nullptr; | |||
1319 | } | |||
1320 | ||||
1321 | /// Write a single indirect call <src, target> pair to the fdata file | |||
1322 | void visitIndCallCounter(IndirectCallHashTable::MapEntry &Entry, | |||
1323 | int FD, int CallsiteID, | |||
1324 | ProfileWriterContext *Ctx) { | |||
1325 | if (Entry.Val == 0) | |||
1326 | return; | |||
1327 | DEBUG(reportNumber("Target func 0x", Entry.Key, 16)){}; | |||
1328 | DEBUG(reportNumber("Target freq: ", Entry.Val, 10)){}; | |||
1329 | const IndCallDescription *CallsiteDesc = | |||
1330 | &Ctx->IndCallDescriptions[CallsiteID]; | |||
1331 | const IndCallTargetDescription *TargetDesc = | |||
1332 | Ctx->lookupIndCallTarget(Entry.Key); | |||
1333 | if (!TargetDesc) { | |||
1334 | DEBUG(report("Failed to lookup indirect call target\n")){}; | |||
1335 | char LineBuf[BufSize]; | |||
1336 | char *Ptr = LineBuf; | |||
1337 | Ptr = serializeLoc(*Ctx, Ptr, *CallsiteDesc, BufSize); | |||
1338 | Ptr = strCopy(Ptr, "0 [unknown] 0 0 ", BufSize - (Ptr - LineBuf) - 40); | |||
1339 | Ptr = intToStr(Ptr, Entry.Val, 10); | |||
1340 | *Ptr++ = '\n'; | |||
1341 | __write(FD, LineBuf, Ptr - LineBuf); | |||
1342 | return; | |||
1343 | } | |||
1344 | Ctx->CallFlowTable->get(TargetDesc->Address).Calls += Entry.Val; | |||
1345 | char LineBuf[BufSize]; | |||
1346 | char *Ptr = LineBuf; | |||
1347 | Ptr = serializeLoc(*Ctx, Ptr, *CallsiteDesc, BufSize); | |||
1348 | Ptr = serializeLoc(*Ctx, Ptr, TargetDesc->Loc, BufSize - (Ptr - LineBuf)); | |||
1349 | Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25); | |||
1350 | Ptr = intToStr(Ptr, Entry.Val, 10); | |||
1351 | *Ptr++ = '\n'; | |||
1352 | __write(FD, LineBuf, Ptr - LineBuf); | |||
1353 | } | |||
1354 | ||||
1355 | /// Write to \p FD all of the indirect call profiles. | |||
1356 | void writeIndirectCallProfile(int FD, ProfileWriterContext &Ctx) { | |||
1357 | for (int I = 0; I < __bolt_instr_num_ind_calls; ++I) { | |||
1358 | DEBUG(reportNumber("IndCallsite #", I, 10)){}; | |||
1359 | GlobalIndCallCounters[I].forEachElement(visitIndCallCounter, FD, I, &Ctx); | |||
1360 | } | |||
1361 | } | |||
1362 | ||||
1363 | /// Check a single call flow for a callee versus all known callers. If there are | |||
1364 | /// less callers than what the callee expects, write the difference with source | |||
1365 | /// [unknown] in the profile. | |||
1366 | void visitCallFlowEntry(CallFlowHashTable::MapEntry &Entry, int FD, | |||
1367 | ProfileWriterContext *Ctx) { | |||
1368 | DEBUG(reportNumber("Call flow entry address: 0x", Entry.Key, 16)){}; | |||
1369 | DEBUG(reportNumber("Calls: ", Entry.Calls, 10)){}; | |||
1370 | DEBUG(reportNumber("Reported entry frequency: ", Entry.Val, 10)){}; | |||
1371 | DEBUG({{} | |||
1372 | if (Entry.Calls > Entry.Val){} | |||
1373 | report(" More calls than expected!\n");{} | |||
1374 | }){}; | |||
1375 | if (Entry.Val <= Entry.Calls) | |||
1376 | return; | |||
1377 | DEBUG(reportNumber({} | |||
1378 | " Balancing calls with traffic: ", Entry.Val - Entry.Calls, 10)){}; | |||
1379 | const IndCallTargetDescription *TargetDesc = | |||
1380 | Ctx->lookupIndCallTarget(Entry.Key); | |||
1381 | if (!TargetDesc) { | |||
1382 | // There is probably something wrong with this callee and this should be | |||
1383 | // investigated, but I don't want to assert and lose all data collected. | |||
1384 | DEBUG(report("WARNING: failed to look up call target!\n")){}; | |||
1385 | return; | |||
1386 | } | |||
1387 | char LineBuf[BufSize]; | |||
1388 | char *Ptr = LineBuf; | |||
1389 | Ptr = strCopy(Ptr, "0 [unknown] 0 ", BufSize); | |||
1390 | Ptr = serializeLoc(*Ctx, Ptr, TargetDesc->Loc, BufSize - (Ptr - LineBuf)); | |||
1391 | Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25); | |||
1392 | Ptr = intToStr(Ptr, Entry.Val - Entry.Calls, 10); | |||
1393 | *Ptr++ = '\n'; | |||
1394 | __write(FD, LineBuf, Ptr - LineBuf); | |||
1395 | } | |||
1396 | ||||
1397 | /// Open fdata file for writing and return a valid file descriptor, aborting | |||
1398 | /// program upon failure. | |||
1399 | int openProfile() { | |||
1400 | // Build the profile name string by appending our PID | |||
1401 | char Buf[BufSize]; | |||
1402 | char *Ptr = Buf; | |||
1403 | uint64_t PID = __getpid(); | |||
1404 | Ptr = strCopy(Buf, __bolt_instr_filename, BufSize); | |||
1405 | if (__bolt_instr_use_pid) { | |||
1406 | Ptr = strCopy(Ptr, ".", BufSize - (Ptr - Buf + 1)); | |||
1407 | Ptr = intToStr(Ptr, PID, 10); | |||
1408 | Ptr = strCopy(Ptr, ".fdata", BufSize - (Ptr - Buf + 1)); | |||
1409 | } | |||
1410 | *Ptr++ = '\0'; | |||
1411 | uint64_t FD = __open(Buf, | |||
1412 | /*flags=*/0x241 /*O_WRONLY|O_TRUNC|O_CREAT*/, | |||
1413 | /*mode=*/0666); | |||
1414 | if (static_cast<int64_t>(FD) < 0) { | |||
1415 | report("Error while trying to open profile file for writing: "); | |||
1416 | report(Buf); | |||
1417 | reportNumber("\nFailed with error number: 0x", | |||
1418 | 0 - static_cast<int64_t>(FD), 16); | |||
1419 | __exit(1); | |||
1420 | } | |||
1421 | return FD; | |||
1422 | } | |||
1423 | ||||
1424 | #endif | |||
1425 | ||||
1426 | } // anonymous namespace | |||
1427 | ||||
1428 | #if !defined(__APPLE__) | |||
1429 | ||||
1430 | /// Reset all counters in case you want to start profiling a new phase of your | |||
1431 | /// program independently of prior phases. | |||
1432 | /// The address of this function is printed by BOLT and this can be called by | |||
1433 | /// any attached debugger during runtime. There is a useful oneliner for gdb: | |||
1434 | /// | |||
1435 | /// gdb -p $(pgrep -xo PROCESSNAME) -ex 'p ((void(*)())0xdeadbeef)()' \ | |||
1436 | /// -ex 'set confirm off' -ex quit | |||
1437 | /// | |||
1438 | /// Where 0xdeadbeef is this function address and PROCESSNAME your binary file | |||
1439 | /// name. | |||
1440 | extern "C" void __bolt_instr_clear_counters() { | |||
1441 | memset(reinterpret_cast<char *>(__bolt_instr_locations), 0, | |||
1442 | __bolt_num_counters * 8); | |||
1443 | for (int I = 0; I < __bolt_instr_num_ind_calls; ++I) | |||
1444 | GlobalIndCallCounters[I].resetCounters(); | |||
1445 | } | |||
1446 | ||||
1447 | /// This is the entry point for profile writing. | |||
1448 | /// There are three ways of getting here: | |||
1449 | /// | |||
1450 | /// * Program execution ended, finalization methods are running and BOLT | |||
1451 | /// hooked into FINI from your binary dynamic section; | |||
1452 | /// * You used the sleep timer option and during initialization we forked | |||
1453 | /// a separete process that will call this function periodically; | |||
1454 | /// * BOLT prints this function address so you can attach a debugger and | |||
1455 | /// call this function directly to get your profile written to disk | |||
1456 | /// on demand. | |||
1457 | /// | |||
1458 | extern "C" void __attribute((force_align_arg_pointer)) | |||
1459 | __bolt_instr_data_dump() { | |||
1460 | // Already dumping | |||
1461 | if (!GlobalWriteProfileMutex->acquire()) | |||
1462 | return; | |||
1463 | ||||
1464 | BumpPtrAllocator HashAlloc; | |||
1465 | HashAlloc.setMaxSize(0x6400000); | |||
1466 | ProfileWriterContext Ctx = readDescriptions(); | |||
1467 | Ctx.CallFlowTable = new (HashAlloc, 0) CallFlowHashTable(HashAlloc); | |||
1468 | ||||
1469 | DEBUG(printStats(Ctx)){}; | |||
1470 | ||||
1471 | int FD = openProfile(); | |||
1472 | ||||
1473 | BumpPtrAllocator Alloc; | |||
1474 | const uint8_t *FuncDesc = Ctx.FuncDescriptions; | |||
1475 | for (int I = 0, E = __bolt_instr_num_funcs; I < E; ++I) { | |||
1476 | FuncDesc = writeFunctionProfile(FD, Ctx, FuncDesc, Alloc); | |||
1477 | Alloc.clear(); | |||
1478 | DEBUG(reportNumber("FuncDesc now: ", (uint64_t)FuncDesc, 16)){}; | |||
1479 | } | |||
1480 | assert(FuncDesc == (void *)Ctx.Strings, | |||
1481 | "FuncDesc ptr must be equal to stringtable"); | |||
1482 | ||||
1483 | writeIndirectCallProfile(FD, Ctx); | |||
1484 | Ctx.CallFlowTable->forEachElement(visitCallFlowEntry, FD, &Ctx); | |||
1485 | ||||
1486 | __fsync(FD); | |||
1487 | __close(FD); | |||
1488 | __munmap(Ctx.MMapPtr, Ctx.MMapSize); | |||
1489 | __close(Ctx.FileDesc); | |||
1490 | HashAlloc.destroy(); | |||
1491 | GlobalWriteProfileMutex->release(); | |||
1492 | DEBUG(report("Finished writing profile.\n")){}; | |||
1493 | } | |||
1494 | ||||
1495 | /// Event loop for our child process spawned during setup to dump profile data | |||
1496 | /// at user-specified intervals | |||
1497 | void watchProcess() { | |||
1498 | timespec ts, rem; | |||
1499 | uint64_t Ellapsed = 0ull; | |||
1500 | uint64_t ppid; | |||
1501 | if (__bolt_instr_wait_forks) { | |||
1502 | // Store parent pgid | |||
1503 | ppid = -__getpgid(0); | |||
1504 | // And leave parent process group | |||
1505 | __setpgid(0, 0); | |||
1506 | } else { | |||
1507 | // Store parent pid | |||
1508 | ppid = __getppid(); | |||
1509 | if (ppid == 1) { | |||
1510 | // Parent already dead | |||
1511 | __bolt_instr_data_dump(); | |||
1512 | goto out; | |||
1513 | } | |||
1514 | } | |||
1515 | ||||
1516 | ts.tv_sec = 1; | |||
1517 | ts.tv_nsec = 0; | |||
1518 | while (1) { | |||
1519 | __nanosleep(&ts, &rem); | |||
1520 | // This means our parent process or all its forks are dead, | |||
1521 | // so no need for us to keep dumping. | |||
1522 | if (__kill(ppid, 0) < 0) { | |||
1523 | if (__bolt_instr_no_counters_clear) | |||
1524 | __bolt_instr_data_dump(); | |||
1525 | break; | |||
1526 | } | |||
1527 | ||||
1528 | if (++Ellapsed < __bolt_instr_sleep_time) | |||
1529 | continue; | |||
1530 | ||||
1531 | Ellapsed = 0; | |||
1532 | __bolt_instr_data_dump(); | |||
1533 | if (__bolt_instr_no_counters_clear == false) | |||
1534 | __bolt_instr_clear_counters(); | |||
1535 | } | |||
1536 | ||||
1537 | out:; | |||
1538 | DEBUG(report("My parent process is dead, bye!\n")){}; | |||
1539 | __exit(0); | |||
1540 | } | |||
1541 | ||||
1542 | extern "C" void __bolt_instr_indirect_call(); | |||
1543 | extern "C" void __bolt_instr_indirect_tailcall(); | |||
1544 | ||||
1545 | /// Initialization code | |||
1546 | extern "C" void __attribute((force_align_arg_pointer)) __bolt_instr_setup() { | |||
1547 | const uint64_t CountersStart = | |||
1548 | reinterpret_cast<uint64_t>(&__bolt_instr_locations[0]); | |||
1549 | const uint64_t CountersEnd = alignTo( | |||
1550 | reinterpret_cast<uint64_t>(&__bolt_instr_locations[__bolt_num_counters]), | |||
1551 | 0x1000); | |||
1552 | DEBUG(reportNumber("replace mmap start: ", CountersStart, 16)){}; | |||
1553 | DEBUG(reportNumber("replace mmap stop: ", CountersEnd, 16)){}; | |||
1554 | assert (CountersEnd > CountersStart, "no counters"); | |||
1555 | // Maps our counters to be shared instead of private, so we keep counting for | |||
1556 | // forked processes | |||
1557 | __mmap(CountersStart, CountersEnd - CountersStart, | |||
1558 | 0x3 /*PROT_READ|PROT_WRITE*/, | |||
1559 | 0x31 /*MAP_ANONYMOUS | MAP_SHARED | MAP_FIXED*/, -1, 0); | |||
1560 | ||||
1561 | __bolt_ind_call_counter_func_pointer = __bolt_instr_indirect_call; | |||
1562 | __bolt_ind_tailcall_counter_func_pointer = __bolt_instr_indirect_tailcall; | |||
1563 | // Conservatively reserve 100MiB shared pages | |||
1564 | GlobalAlloc.setMaxSize(0x6400000); | |||
1565 | GlobalAlloc.setShared(true); | |||
1566 | GlobalWriteProfileMutex = new (GlobalAlloc, 0) Mutex(); | |||
1567 | if (__bolt_instr_num_ind_calls > 0) | |||
1568 | GlobalIndCallCounters = | |||
1569 | new (GlobalAlloc, 0) IndirectCallHashTable[__bolt_instr_num_ind_calls]; | |||
1570 | ||||
1571 | if (__bolt_instr_sleep_time != 0) { | |||
1572 | // Separate instrumented process to the own process group | |||
1573 | if (__bolt_instr_wait_forks) | |||
1574 | __setpgid(0, 0); | |||
1575 | ||||
1576 | if (long PID = __fork()) | |||
1577 | return; | |||
1578 | watchProcess(); | |||
1579 | } | |||
1580 | } | |||
1581 | ||||
1582 | extern "C" __attribute((force_align_arg_pointer)) void | |||
1583 | instrumentIndirectCall(uint64_t Target, uint64_t IndCallID) { | |||
1584 | GlobalIndCallCounters[IndCallID].incrementVal(Target, GlobalAlloc); | |||
1585 | } | |||
1586 | ||||
1587 | /// We receive as in-stack arguments the identifier of the indirect call site | |||
1588 | /// as well as the target address for the call | |||
1589 | extern "C" __attribute((naked)) void __bolt_instr_indirect_call() | |||
1590 | { | |||
1591 | __asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n" "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n" "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n" "sub $8, %%rsp\n" | |||
1592 | "mov 0xa0(%%rsp), %%rdi\n" | |||
1593 | "mov 0x98(%%rsp), %%rsi\n" | |||
1594 | "call instrumentIndirectCall\n" | |||
1595 | RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n" "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n" "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n" "pop %%rax\n" | |||
1596 | "ret\n" | |||
1597 | :::); | |||
1598 | } | |||
1599 | ||||
1600 | extern "C" __attribute((naked)) void __bolt_instr_indirect_tailcall() | |||
1601 | { | |||
1602 | __asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n" "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n" "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n" "sub $8, %%rsp\n" | |||
1603 | "mov 0x98(%%rsp), %%rdi\n" | |||
1604 | "mov 0x90(%%rsp), %%rsi\n" | |||
1605 | "call instrumentIndirectCall\n" | |||
1606 | RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n" "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n" "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n" "pop %%rax\n" | |||
1607 | "ret\n" | |||
1608 | :::); | |||
1609 | } | |||
1610 | ||||
1611 | /// This is hooking ELF's entry, it needs to save all machine state. | |||
1612 | extern "C" __attribute((naked)) void __bolt_instr_start() | |||
1613 | { | |||
1614 | __asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n" "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n" "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n" "sub $8, %%rsp\n" | |||
1615 | "call __bolt_instr_setup\n" | |||
1616 | RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n" "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n" "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n" "pop %%rax\n" | |||
1617 | "jmp __bolt_start_trampoline\n" | |||
1618 | :::); | |||
1619 | } | |||
1620 | ||||
1621 | /// This is hooking into ELF's DT_FINI | |||
1622 | extern "C" void __bolt_instr_fini() { | |||
1623 | __bolt_fini_trampoline(); | |||
1624 | if (__bolt_instr_sleep_time == 0) | |||
1625 | __bolt_instr_data_dump(); | |||
1626 | DEBUG(report("Finished.\n")){}; | |||
1627 | } | |||
1628 | ||||
1629 | #endif | |||
1630 | ||||
1631 | #if defined(__APPLE__) | |||
1632 | ||||
1633 | extern "C" void __bolt_instr_data_dump() { | |||
1634 | ProfileWriterContext Ctx = readDescriptions(); | |||
1635 | ||||
1636 | int FD = 2; | |||
1637 | BumpPtrAllocator Alloc; | |||
1638 | const uint8_t *FuncDesc = Ctx.FuncDescriptions; | |||
1639 | uint32_t bolt_instr_num_funcs = _bolt_instr_num_funcs_getter(); | |||
1640 | ||||
1641 | for (int I = 0, E = bolt_instr_num_funcs; I < E; ++I) { | |||
1642 | FuncDesc = writeFunctionProfile(FD, Ctx, FuncDesc, Alloc); | |||
1643 | Alloc.clear(); | |||
1644 | DEBUG(reportNumber("FuncDesc now: ", (uint64_t)FuncDesc, 16)){}; | |||
1645 | } | |||
1646 | assert(FuncDesc == (void *)Ctx.Strings, | |||
1647 | "FuncDesc ptr must be equal to stringtable"); | |||
1648 | } | |||
1649 | ||||
1650 | // On OSX/iOS the final symbol name of an extern "C" function/variable contains | |||
1651 | // one extra leading underscore: _bolt_instr_setup -> __bolt_instr_setup. | |||
1652 | extern "C" | |||
1653 | __attribute__((section("__TEXT,__setup"))) | |||
1654 | __attribute__((force_align_arg_pointer)) | |||
1655 | void _bolt_instr_setup() { | |||
1656 | __asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n" "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n" "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n" "sub $8, %%rsp\n" :::); | |||
1657 | ||||
1658 | report("Hello!\n"); | |||
1659 | ||||
1660 | __asm__ __volatile__(RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n" "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n" "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n" "pop %%rax\n" :::); | |||
1661 | } | |||
1662 | ||||
1663 | extern "C" | |||
1664 | __attribute__((section("__TEXT,__fini"))) | |||
1665 | __attribute__((force_align_arg_pointer)) | |||
1666 | void _bolt_instr_fini() { | |||
1667 | report("Bye!\n"); | |||
1668 | __bolt_instr_data_dump(); | |||
1669 | } | |||
1670 | ||||
1671 | #endif | |||
1672 | #endif |