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

source code of bolt/runtime/instr.cpp