//===- bolt/runtime/instr.cpp ---------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // BOLT runtime instrumentation library for x86 Linux. Currently, BOLT does // not support linking modules with dependencies on one another into the final // binary (TODO?), which means this library has to be self-contained in a single // module. // // All extern declarations here need to be defined by BOLT itself. Those will be // undefined symbols that BOLT needs to resolve by emitting these symbols with // MCStreamer. Currently, Passes/Instrumentation.cpp is the pass responsible // for defining the symbols here and these two files have a tight coupling: one // working statically when you run BOLT and another during program runtime when // you run an instrumented binary. The main goal here is to output an fdata file // (BOLT profile) with the instrumentation counters inserted by the static pass. // Counters for indirect calls are an exception, as we can't know them // statically. These counters are created and managed here. To allow this, we // need a minimal framework for allocating memory dynamically. We provide this // with the BumpPtrAllocator class (not LLVM's, but our own version of it). // // Since this code is intended to be inserted into any executable, we decided to // make it standalone and do not depend on any external libraries (i.e. language // support libraries, such as glibc or stdc++). To allow this, we provide a few // light implementations of common OS interacting functionalities using direct // syscall wrappers. Our simple allocator doesn't manage deallocations that // fragment the memory space, so it's stack based. This is the minimal framework // provided here to allow processing instrumented counters and writing fdata. // // In the C++ idiom used here, we never use or rely on constructors or // destructors for global objects. That's because those need support from the // linker in initialization/finalization code, and we want to keep our linker // very simple. Similarly, we don't create any global objects that are zero // initialized, since those would need to go .bss, which our simple linker also // don't support (TODO?). // //===----------------------------------------------------------------------===// #include "common.h" // Enables a very verbose logging to stderr useful when debugging //#define ENABLE_DEBUG #ifdef ENABLE_DEBUG #define DEBUG(X) \ { X; } #else #define DEBUG(X) \ {} #endif #pragma GCC visibility push(hidden) extern "C" { #if defined(__APPLE__) extern uint64_t* _bolt_instr_locations_getter(); extern uint32_t _bolt_num_counters_getter(); extern uint8_t* _bolt_instr_tables_getter(); extern uint32_t _bolt_instr_num_funcs_getter(); #else // Main counters inserted by instrumentation, incremented during runtime when // points of interest (locations) in the program are reached. Those are direct // calls and direct and indirect branches (local ones). There are also counters // for basic block execution if they are a spanning tree leaf and need to be // counted in order to infer the execution count of other edges of the CFG. extern uint64_t __bolt_instr_locations[]; extern uint32_t __bolt_num_counters; // Descriptions are serialized metadata about binary functions written by BOLT, // so we have a minimal understanding about the program structure. For a // reference on the exact format of this metadata, see *Description structs, // Location, IntrumentedNode and EntryNode. // Number of indirect call site descriptions extern uint32_t __bolt_instr_num_ind_calls; // Number of indirect call target descriptions extern uint32_t __bolt_instr_num_ind_targets; // Number of function descriptions extern uint32_t __bolt_instr_num_funcs; // Time to sleep across dumps (when we write the fdata profile to disk) extern uint32_t __bolt_instr_sleep_time; // Do not clear counters across dumps, rewrite file with the updated values extern bool __bolt_instr_no_counters_clear; // Wait until all forks of instrumented process will finish extern bool __bolt_instr_wait_forks; // Filename to dump data to extern char __bolt_instr_filename[]; // Instumented binary file path extern char __bolt_instr_binpath[]; // If true, append current PID to the fdata filename when creating it so // different invocations of the same program can be differentiated. extern bool __bolt_instr_use_pid; // Functions that will be used to instrument indirect calls. BOLT static pass // will identify indirect calls and modify them to load the address in these // trampolines and call this address instead. BOLT can't use direct calls to // our handlers because our addresses here are not known at analysis time. We // only support resolving dependencies from this file to the output of BOLT, // *not* the other way around. // TODO: We need better linking support to make that happen. extern void (*__bolt_ind_call_counter_func_pointer)(); extern void (*__bolt_ind_tailcall_counter_func_pointer)(); // Function pointers to init/fini trampoline routines in the binary, so we can // resume regular execution of these functions that we hooked extern void __bolt_start_trampoline(); extern void __bolt_fini_trampoline(); #endif } namespace { /// A simple allocator that mmaps a fixed size region and manages this space /// in a stack fashion, meaning you always deallocate the last element that /// was allocated. In practice, we don't need to deallocate individual elements. /// We monotonically increase our usage and then deallocate everything once we /// are done processing something. class BumpPtrAllocator { /// This is written before each allocation and act as a canary to detect when /// a bug caused our program to cross allocation boundaries. struct EntryMetadata { uint64_t Magic; uint64_t AllocSize; }; public: void *allocate(size_t Size) { Lock L(M); if (StackBase == nullptr) { StackBase = reinterpret_cast( __mmap(0, MaxSize, PROT_READ | PROT_WRITE, (Shared ? MAP_SHARED : MAP_PRIVATE) | MAP_ANONYMOUS, -1, 0)); assert(StackBase != MAP_FAILED, "BumpPtrAllocator: failed to mmap stack!"); StackSize = 0; } Size = alignTo(Size + sizeof(EntryMetadata), 16); uint8_t *AllocAddress = StackBase + StackSize + sizeof(EntryMetadata); auto *M = reinterpret_cast(StackBase + StackSize); M->Magic = Magic; M->AllocSize = Size; StackSize += Size; assert(StackSize < MaxSize, "allocator ran out of memory"); return AllocAddress; } #ifdef DEBUG /// Element-wise deallocation is only used for debugging to catch memory /// bugs by checking magic bytes. Ordinarily, we reset the allocator once /// we are done with it. Reset is done with clear(). There's no need /// to deallocate each element individually. void deallocate(void *Ptr) { Lock L(M); uint8_t MetadataOffset = sizeof(EntryMetadata); auto *M = reinterpret_cast( reinterpret_cast(Ptr) - MetadataOffset); const uint8_t *StackTop = StackBase + StackSize + MetadataOffset; // Validate size if (Ptr != StackTop - M->AllocSize) { // Failed validation, check if it is a pointer returned by operator new [] MetadataOffset += sizeof(uint64_t); // Space for number of elements alloc'ed M = reinterpret_cast(reinterpret_cast(Ptr) - MetadataOffset); // Ok, it failed both checks if this assertion fails. Stop the program, we // have a memory bug. assert(Ptr == StackTop - M->AllocSize, "must deallocate the last element alloc'ed"); } assert(M->Magic == Magic, "allocator magic is corrupt"); StackSize -= M->AllocSize; } #else void deallocate(void *) {} #endif void clear() { Lock L(M); StackSize = 0; } /// Set mmap reservation size (only relevant before first allocation) void setMaxSize(uint64_t Size) { MaxSize = Size; } /// Set mmap reservation privacy (only relevant before first allocation) void setShared(bool S) { Shared = S; } void destroy() { if (StackBase == nullptr) return; __munmap(StackBase, MaxSize); } // Placement operator to construct allocator in possibly shared mmaped memory static void *operator new(size_t, void *Ptr) { return Ptr; }; private: static constexpr uint64_t Magic = 0x1122334455667788ull; uint64_t MaxSize = 0xa00000; uint8_t *StackBase{nullptr}; uint64_t StackSize{0}; bool Shared{false}; Mutex M; }; /// Used for allocating indirect call instrumentation counters. Initialized by /// __bolt_instr_setup, our initialization routine. BumpPtrAllocator *GlobalAlloc; // Base address which we substract from recorded PC values when searching for // indirect call description entries. Needed because indCall descriptions are // mapped read-only and contain static addresses. Initialized in // __bolt_instr_setup. uint64_t TextBaseAddress = 0; // Storage for GlobalAlloc which can be shared if not using // instrumentation-file-append-pid. void *GlobalMetadataStorage; } // anonymous namespace // User-defined placement new operators. We only use those (as opposed to // overriding the regular operator new) so we can keep our allocator in the // stack instead of in a data section (global). void *operator new(size_t Sz, BumpPtrAllocator &A) { return A.allocate(Sz); } void *operator new(size_t Sz, BumpPtrAllocator &A, char C) { auto *Ptr = reinterpret_cast(A.allocate(Sz)); memset(Ptr, C, Sz); return Ptr; } void *operator new[](size_t Sz, BumpPtrAllocator &A) { return A.allocate(Sz); } void *operator new[](size_t Sz, BumpPtrAllocator &A, char C) { auto *Ptr = reinterpret_cast(A.allocate(Sz)); memset(Ptr, C, Sz); return Ptr; } // Only called during exception unwinding (useless). We must manually dealloc. // C++ language weirdness void operator delete(void *Ptr, BumpPtrAllocator &A) { A.deallocate(Ptr); } namespace { // Disable instrumentation optimizations that sacrifice profile accuracy extern "C" bool __bolt_instr_conservative; /// Basic key-val atom stored in our hash struct SimpleHashTableEntryBase { uint64_t Key; uint64_t Val; void dump(const char *Msg = nullptr) { // TODO: make some sort of formatting function // Currently we have to do it the ugly way because // we want every message to be printed atomically via a single call to // __write. If we use reportNumber() and others nultiple times, we'll get // garbage in mulithreaded environment char Buf[BufSize]; char *Ptr = Buf; Ptr = intToStr(Ptr, __getpid(), 10); *Ptr++ = ':'; *Ptr++ = ' '; if (Msg) Ptr = strCopy(Ptr, Msg, strLen(Msg)); *Ptr++ = '0'; *Ptr++ = 'x'; Ptr = intToStr(Ptr, (uint64_t)this, 16); *Ptr++ = ':'; *Ptr++ = ' '; Ptr = strCopy(Ptr, "MapEntry(0x", sizeof("MapEntry(0x") - 1); Ptr = intToStr(Ptr, Key, 16); *Ptr++ = ','; *Ptr++ = ' '; *Ptr++ = '0'; *Ptr++ = 'x'; Ptr = intToStr(Ptr, Val, 16); *Ptr++ = ')'; *Ptr++ = '\n'; assert(Ptr - Buf < BufSize, "Buffer overflow!"); // print everything all at once for atomicity __write(2, Buf, Ptr - Buf); } }; /// This hash table implementation starts by allocating a table of size /// InitialSize. When conflicts happen in this main table, it resolves /// them by chaining a new table of size IncSize. It never reallocs as our /// allocator doesn't support it. The key is intended to be function pointers. /// There's no clever hash function (it's just x mod size, size being prime). /// I never tuned the coefficientes in the modular equation (TODO) /// This is used for indirect calls (each call site has one of this, so it /// should have a small footprint) and for tallying call counts globally for /// each target to check if we missed the origin of some calls (this one is a /// large instantiation of this template, since it is global for all call sites) template class SimpleHashTable { public: using MapEntry = T; /// Increment by 1 the value of \p Key. If it is not in this table, it will be /// added to the table and its value set to 1. void incrementVal(uint64_t Key, BumpPtrAllocator &Alloc) { if (!__bolt_instr_conservative) { TryLock L(M); if (!L.isLocked()) return; auto &E = getOrAllocEntry(Key, Alloc); ++E.Val; return; } Lock L(M); auto &E = getOrAllocEntry(Key, Alloc); ++E.Val; } /// Basic member accessing interface. Here we pass the allocator explicitly to /// avoid storing a pointer to it as part of this table (remember there is one /// hash for each indirect call site, so we want to minimize our footprint). MapEntry &get(uint64_t Key, BumpPtrAllocator &Alloc) { if (!__bolt_instr_conservative) { TryLock L(M); if (!L.isLocked()) return NoEntry; return getOrAllocEntry(Key, Alloc); } Lock L(M); return getOrAllocEntry(Key, Alloc); } /// Traverses all elements in the table template void forEachElement(void (*Callback)(MapEntry &, Args...), Args... args) { Lock L(M); if (!TableRoot) return; return forEachElement(Callback, InitialSize, TableRoot, args...); } void resetCounters(); private: constexpr static uint64_t VacantMarker = 0; constexpr static uint64_t FollowUpTableMarker = 0x8000000000000000ull; MapEntry *TableRoot{nullptr}; MapEntry NoEntry; Mutex M; template void forEachElement(void (*Callback)(MapEntry &, Args...), uint32_t NumEntries, MapEntry *Entries, Args... args) { for (uint32_t I = 0; I < NumEntries; ++I) { MapEntry &Entry = Entries[I]; if (Entry.Key == VacantMarker) continue; if (Entry.Key & FollowUpTableMarker) { MapEntry *Next = reinterpret_cast(Entry.Key & ~FollowUpTableMarker); assert(Next != Entries, "Circular reference!"); forEachElement(Callback, IncSize, Next, args...); continue; } Callback(Entry, args...); } } MapEntry &firstAllocation(uint64_t Key, BumpPtrAllocator &Alloc) { TableRoot = new (Alloc, 0) MapEntry[InitialSize]; MapEntry &Entry = TableRoot[Key % InitialSize]; Entry.Key = Key; // DEBUG(Entry.dump("Created root entry: ")); return Entry; } MapEntry &getEntry(MapEntry *Entries, uint64_t Key, uint64_t Selector, BumpPtrAllocator &Alloc, int CurLevel) { // DEBUG(reportNumber("getEntry called, level ", CurLevel, 10)); const uint32_t NumEntries = CurLevel == 0 ? InitialSize : IncSize; uint64_t Remainder = Selector / NumEntries; Selector = Selector % NumEntries; MapEntry &Entry = Entries[Selector]; // A hit if (Entry.Key == Key) { // DEBUG(Entry.dump("Hit: ")); return Entry; } // Vacant - add new entry if (Entry.Key == VacantMarker) { Entry.Key = Key; // DEBUG(Entry.dump("Adding new entry: ")); return Entry; } // Defer to the next level if (Entry.Key & FollowUpTableMarker) { return getEntry( reinterpret_cast(Entry.Key & ~FollowUpTableMarker), Key, Remainder, Alloc, CurLevel + 1); } // Conflict - create the next level // DEBUG(Entry.dump("Creating new level: ")); MapEntry *NextLevelTbl = new (Alloc, 0) MapEntry[IncSize]; // DEBUG( // reportNumber("Newly allocated level: 0x", uint64_t(NextLevelTbl), // 16)); uint64_t CurEntrySelector = Entry.Key / InitialSize; for (int I = 0; I < CurLevel; ++I) CurEntrySelector /= IncSize; CurEntrySelector = CurEntrySelector % IncSize; NextLevelTbl[CurEntrySelector] = Entry; Entry.Key = reinterpret_cast(NextLevelTbl) | FollowUpTableMarker; assert((NextLevelTbl[CurEntrySelector].Key & ~FollowUpTableMarker) != uint64_t(Entries), "circular reference created!\n"); // DEBUG(NextLevelTbl[CurEntrySelector].dump("New level entry: ")); // DEBUG(Entry.dump("Updated old entry: ")); return getEntry(NextLevelTbl, Key, Remainder, Alloc, CurLevel + 1); } MapEntry &getOrAllocEntry(uint64_t Key, BumpPtrAllocator &Alloc) { if (TableRoot) { MapEntry &E = getEntry(TableRoot, Key, Key, Alloc, 0); assert(!(E.Key & FollowUpTableMarker), "Invalid entry!"); return E; } return firstAllocation(Key, Alloc); } }; template void resetIndCallCounter(T &Entry) { Entry.Val = 0; } template void SimpleHashTable::resetCounters() { forEachElement(resetIndCallCounter); } /// Represents a hash table mapping a function target address to its counter. using IndirectCallHashTable = SimpleHashTable<>; /// Initialize with number 1 instead of 0 so we don't go into .bss. This is the /// global array of all hash tables storing indirect call destinations happening /// during runtime, one table per call site. IndirectCallHashTable *GlobalIndCallCounters{ reinterpret_cast(1)}; /// Don't allow reentrancy in the fdata writing phase - only one thread writes /// it Mutex *GlobalWriteProfileMutex{reinterpret_cast(1)}; /// Store number of calls in additional to target address (Key) and frequency /// as perceived by the basic block counter (Val). struct CallFlowEntryBase : public SimpleHashTableEntryBase { uint64_t Calls; }; using CallFlowHashTableBase = SimpleHashTable; /// This is a large table indexing all possible call targets (indirect and /// direct ones). The goal is to find mismatches between number of calls (for /// those calls we were able to track) and the entry basic block counter of the /// callee. In most cases, these two should be equal. If not, there are two /// possible scenarios here: /// /// * Entry BB has higher frequency than all known calls to this function. /// In this case, we have dynamic library code or any uninstrumented code /// calling this function. We will write the profile for these untracked /// calls as having source "0 [unknown] 0" in the fdata file. /// /// * Number of known calls is higher than the frequency of entry BB /// This only happens when there is no counter for the entry BB / callee /// function is not simple (in BOLT terms). We don't do anything special /// here and just ignore those (we still report all calls to the non-simple /// function, though). /// class CallFlowHashTable : public CallFlowHashTableBase { public: CallFlowHashTable(BumpPtrAllocator &Alloc) : Alloc(Alloc) {} MapEntry &get(uint64_t Key) { return CallFlowHashTableBase::get(Key, Alloc); } private: // Different than the hash table for indirect call targets, we do store the // allocator here since there is only one call flow hash and space overhead // is negligible. BumpPtrAllocator &Alloc; }; /// /// Description metadata emitted by BOLT to describe the program - refer to /// Passes/Instrumentation.cpp - Instrumentation::emitTablesAsELFNote() /// struct Location { uint32_t FunctionName; uint32_t Offset; }; struct CallDescription { Location From; uint32_t FromNode; Location To; uint32_t Counter; uint64_t TargetAddress; }; using IndCallDescription = Location; struct IndCallTargetDescription { Location Loc; uint64_t Address; }; struct EdgeDescription { Location From; uint32_t FromNode; Location To; uint32_t ToNode; uint32_t Counter; }; struct InstrumentedNode { uint32_t Node; uint32_t Counter; }; struct EntryNode { uint64_t Node; uint64_t Address; }; struct FunctionDescription { uint32_t NumLeafNodes; const InstrumentedNode *LeafNodes; uint32_t NumEdges; const EdgeDescription *Edges; uint32_t NumCalls; const CallDescription *Calls; uint32_t NumEntryNodes; const EntryNode *EntryNodes; /// Constructor will parse the serialized function metadata written by BOLT FunctionDescription(const uint8_t *FuncDesc); uint64_t getSize() const { return 16 + NumLeafNodes * sizeof(InstrumentedNode) + NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription) + NumEntryNodes * sizeof(EntryNode); } }; /// The context is created when the fdata profile needs to be written to disk /// and we need to interpret our runtime counters. It contains pointers to the /// mmaped binary (only the BOLT written metadata section). Deserialization /// should be straightforward as most data is POD or an array of POD elements. /// This metadata is used to reconstruct function CFGs. struct ProfileWriterContext { IndCallDescription *IndCallDescriptions; IndCallTargetDescription *IndCallTargets; uint8_t *FuncDescriptions; char *Strings; // String table with function names used in this binary int FileDesc; // File descriptor for the file on disk backing this // information in memory via mmap void *MMapPtr; // The mmap ptr int MMapSize; // The mmap size /// Hash table storing all possible call destinations to detect untracked /// calls and correctly report them as [unknown] in output fdata. CallFlowHashTable *CallFlowTable; /// Lookup the sorted indirect call target vector to fetch function name and /// offset for an arbitrary function pointer. const IndCallTargetDescription *lookupIndCallTarget(uint64_t Target) const; }; /// Perform a string comparison and returns zero if Str1 matches Str2. Compares /// at most Size characters. int compareStr(const char *Str1, const char *Str2, int Size) { while (*Str1 == *Str2) { if (*Str1 == '\0' || --Size == 0) return 0; ++Str1; ++Str2; } return 1; } /// Output Location to the fdata file char *serializeLoc(const ProfileWriterContext &Ctx, char *OutBuf, const Location Loc, uint32_t BufSize) { // fdata location format: Type Name Offset // Type 1 - regular symbol OutBuf = strCopy(OutBuf, "1 "); const char *Str = Ctx.Strings + Loc.FunctionName; uint32_t Size = 25; while (*Str) { *OutBuf++ = *Str++; if (++Size >= BufSize) break; } assert(!*Str, "buffer overflow, function name too large"); *OutBuf++ = ' '; OutBuf = intToStr(OutBuf, Loc.Offset, 16); *OutBuf++ = ' '; return OutBuf; } /// Read and deserialize a function description written by BOLT. \p FuncDesc /// points at the beginning of the function metadata structure in the file. /// See Instrumentation::emitTablesAsELFNote() FunctionDescription::FunctionDescription(const uint8_t *FuncDesc) { NumLeafNodes = *reinterpret_cast(FuncDesc); DEBUG(reportNumber("NumLeafNodes = ", NumLeafNodes, 10)); LeafNodes = reinterpret_cast(FuncDesc + 4); NumEdges = *reinterpret_cast( FuncDesc + 4 + NumLeafNodes * sizeof(InstrumentedNode)); DEBUG(reportNumber("NumEdges = ", NumEdges, 10)); Edges = reinterpret_cast( FuncDesc + 8 + NumLeafNodes * sizeof(InstrumentedNode)); NumCalls = *reinterpret_cast( FuncDesc + 8 + NumLeafNodes * sizeof(InstrumentedNode) + NumEdges * sizeof(EdgeDescription)); DEBUG(reportNumber("NumCalls = ", NumCalls, 10)); Calls = reinterpret_cast( FuncDesc + 12 + NumLeafNodes * sizeof(InstrumentedNode) + NumEdges * sizeof(EdgeDescription)); NumEntryNodes = *reinterpret_cast( FuncDesc + 12 + NumLeafNodes * sizeof(InstrumentedNode) + NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription)); DEBUG(reportNumber("NumEntryNodes = ", NumEntryNodes, 10)); EntryNodes = reinterpret_cast( FuncDesc + 16 + NumLeafNodes * sizeof(InstrumentedNode) + NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription)); } /// Read and mmap descriptions written by BOLT from the executable's notes /// section #if defined(HAVE_ELF_H) and !defined(__APPLE__) void *__attribute__((noinline)) __get_pc() { return __builtin_extract_return_addr(__builtin_return_address(0)); } /// Get string with address and parse it to hex pair bool parseAddressRange(const char *Str, uint64_t &StartAddress, uint64_t &EndAddress) { if (!Str) return false; // Parsed string format: - StartAddress = hexToLong(Str, '-'); while (*Str && *Str != '-') ++Str; if (!*Str) return false; ++Str; // swallow '-' EndAddress = hexToLong(Str); return true; } /// Get full path to the real binary by getting current virtual address /// and searching for the appropriate link in address range in /// /proc/self/map_files static char *getBinaryPath() { const uint32_t BufSize = 1024; const uint32_t NameMax = 4096; const char DirPath[] = "/proc/self/map_files/"; static char TargetPath[NameMax] = {}; char Buf[BufSize]; if (__bolt_instr_binpath[0] != '\0') return __bolt_instr_binpath; if (TargetPath[0] != '\0') return TargetPath; unsigned long CurAddr = (unsigned long)__get_pc(); uint64_t FDdir = __open(DirPath, O_RDONLY, /*mode=*/0666); assert(static_cast(FDdir) >= 0, "failed to open /proc/self/map_files"); while (long Nread = __getdents64(FDdir, (struct dirent64 *)Buf, BufSize)) { assert(static_cast(Nread) != -1, "failed to get folder entries"); struct dirent64 *d; for (long Bpos = 0; Bpos < Nread; Bpos += d->d_reclen) { d = (struct dirent64 *)(Buf + Bpos); uint64_t StartAddress, EndAddress; if (!parseAddressRange(d->d_name, StartAddress, EndAddress)) continue; if (CurAddr < StartAddress || CurAddr > EndAddress) continue; char FindBuf[NameMax]; char *C = strCopy(FindBuf, DirPath, NameMax); C = strCopy(C, d->d_name, NameMax - (C - FindBuf)); *C = '\0'; uint32_t Ret = __readlink(FindBuf, TargetPath, sizeof(TargetPath)); assert(Ret != -1 && Ret != BufSize, "readlink error"); TargetPath[Ret] = '\0'; return TargetPath; } } return nullptr; } ProfileWriterContext readDescriptions() { ProfileWriterContext Result; char *BinPath = getBinaryPath(); assert(BinPath && BinPath[0] != '\0', "failed to find binary path"); uint64_t FD = __open(BinPath, O_RDONLY, /*mode=*/0666); assert(static_cast(FD) >= 0, "failed to open binary path"); Result.FileDesc = FD; // mmap our binary to memory uint64_t Size = __lseek(FD, 0, SEEK_END); uint8_t *BinContents = reinterpret_cast( __mmap(0, Size, PROT_READ, MAP_PRIVATE, FD, 0)); assert(BinContents != MAP_FAILED, "readDescriptions: Failed to mmap self!"); Result.MMapPtr = BinContents; Result.MMapSize = Size; Elf64_Ehdr *Hdr = reinterpret_cast(BinContents); Elf64_Shdr *Shdr = reinterpret_cast(BinContents + Hdr->e_shoff); Elf64_Shdr *StringTblHeader = reinterpret_cast( BinContents + Hdr->e_shoff + Hdr->e_shstrndx * Hdr->e_shentsize); // Find .bolt.instr.tables with the data we need and set pointers to it for (int I = 0; I < Hdr->e_shnum; ++I) { char *SecName = reinterpret_cast( BinContents + StringTblHeader->sh_offset + Shdr->sh_name); if (compareStr(SecName, ".bolt.instr.tables", 64) != 0) { Shdr = reinterpret_cast(BinContents + Hdr->e_shoff + (I + 1) * Hdr->e_shentsize); continue; } // Actual contents of the ELF note start after offset 20 decimal: // Offset 0: Producer name size (4 bytes) // Offset 4: Contents size (4 bytes) // Offset 8: Note type (4 bytes) // Offset 12: Producer name (BOLT\0) (5 bytes + align to 4-byte boundary) // Offset 20: Contents uint32_t IndCallDescSize = *reinterpret_cast(BinContents + Shdr->sh_offset + 20); uint32_t IndCallTargetDescSize = *reinterpret_cast( BinContents + Shdr->sh_offset + 24 + IndCallDescSize); uint32_t FuncDescSize = *reinterpret_cast(BinContents + Shdr->sh_offset + 28 + IndCallDescSize + IndCallTargetDescSize); Result.IndCallDescriptions = reinterpret_cast( BinContents + Shdr->sh_offset + 24); Result.IndCallTargets = reinterpret_cast( BinContents + Shdr->sh_offset + 28 + IndCallDescSize); Result.FuncDescriptions = BinContents + Shdr->sh_offset + 32 + IndCallDescSize + IndCallTargetDescSize; Result.Strings = reinterpret_cast( BinContents + Shdr->sh_offset + 32 + IndCallDescSize + IndCallTargetDescSize + FuncDescSize); return Result; } const char ErrMsg[] = "BOLT instrumentation runtime error: could not find section " ".bolt.instr.tables\n"; reportError(ErrMsg, sizeof(ErrMsg)); return Result; } #else ProfileWriterContext readDescriptions() { ProfileWriterContext Result; uint8_t *Tables = _bolt_instr_tables_getter(); uint32_t IndCallDescSize = *reinterpret_cast(Tables); uint32_t IndCallTargetDescSize = *reinterpret_cast(Tables + 4 + IndCallDescSize); uint32_t FuncDescSize = *reinterpret_cast( Tables + 8 + IndCallDescSize + IndCallTargetDescSize); Result.IndCallDescriptions = reinterpret_cast(Tables + 4); Result.IndCallTargets = reinterpret_cast( Tables + 8 + IndCallDescSize); Result.FuncDescriptions = Tables + 12 + IndCallDescSize + IndCallTargetDescSize; Result.Strings = reinterpret_cast( Tables + 12 + IndCallDescSize + IndCallTargetDescSize + FuncDescSize); return Result; } #endif #if !defined(__APPLE__) /// Debug by printing overall metadata global numbers to check it is sane void printStats(const ProfileWriterContext &Ctx) { char StatMsg[BufSize]; char *StatPtr = StatMsg; StatPtr = strCopy(StatPtr, "\nBOLT INSTRUMENTATION RUNTIME STATISTICS\n\nIndCallDescSize: "); StatPtr = intToStr(StatPtr, Ctx.FuncDescriptions - reinterpret_cast(Ctx.IndCallDescriptions), 10); StatPtr = strCopy(StatPtr, "\nFuncDescSize: "); StatPtr = intToStr( StatPtr, reinterpret_cast(Ctx.Strings) - Ctx.FuncDescriptions, 10); StatPtr = strCopy(StatPtr, "\n__bolt_instr_num_ind_calls: "); StatPtr = intToStr(StatPtr, __bolt_instr_num_ind_calls, 10); StatPtr = strCopy(StatPtr, "\n__bolt_instr_num_funcs: "); StatPtr = intToStr(StatPtr, __bolt_instr_num_funcs, 10); StatPtr = strCopy(StatPtr, "\n"); __write(2, StatMsg, StatPtr - StatMsg); } #endif /// This is part of a simple CFG representation in memory, where we store /// a dynamically sized array of input and output edges per node, and store /// a dynamically sized array of nodes per graph. We also store the spanning /// tree edges for that CFG in a separate array of nodes in /// \p SpanningTreeNodes, while the regular nodes live in \p CFGNodes. struct Edge { uint32_t Node; // Index in nodes array regarding the destination of this edge uint32_t ID; // Edge index in an array comprising all edges of the graph }; /// A regular graph node or a spanning tree node struct Node { uint32_t NumInEdges{0}; // Input edge count used to size InEdge uint32_t NumOutEdges{0}; // Output edge count used to size OutEdges Edge *InEdges{nullptr}; // Created and managed by \p Graph Edge *OutEdges{nullptr}; // ditto }; /// Main class for CFG representation in memory. Manages object creation and /// destruction, populates an array of CFG nodes as well as corresponding /// spanning tree nodes. struct Graph { uint32_t NumNodes; Node *CFGNodes; Node *SpanningTreeNodes; uint64_t *EdgeFreqs; uint64_t *CallFreqs; BumpPtrAllocator &Alloc; const FunctionDescription &D; /// Reads a list of edges from function description \p D and builds /// the graph from it. Allocates several internal dynamic structures that are /// later destroyed by ~Graph() and uses \p Alloc. D.LeafNodes contain all /// spanning tree leaf nodes descriptions (their counters). They are the seed /// used to compute the rest of the missing edge counts in a bottom-up /// traversal of the spanning tree. Graph(BumpPtrAllocator &Alloc, const FunctionDescription &D, const uint64_t *Counters, ProfileWriterContext &Ctx); ~Graph(); void dump() const; private: void computeEdgeFrequencies(const uint64_t *Counters, ProfileWriterContext &Ctx); void dumpEdgeFreqs() const; }; Graph::Graph(BumpPtrAllocator &Alloc, const FunctionDescription &D, const uint64_t *Counters, ProfileWriterContext &Ctx) : Alloc(Alloc), D(D) { DEBUG(reportNumber("G = 0x", (uint64_t)this, 16)); // First pass to determine number of nodes int32_t MaxNodes = -1; CallFreqs = nullptr; EdgeFreqs = nullptr; for (int I = 0; I < D.NumEdges; ++I) { if (static_cast(D.Edges[I].FromNode) > MaxNodes) MaxNodes = D.Edges[I].FromNode; if (static_cast(D.Edges[I].ToNode) > MaxNodes) MaxNodes = D.Edges[I].ToNode; } for (int I = 0; I < D.NumLeafNodes; ++I) if (static_cast(D.LeafNodes[I].Node) > MaxNodes) MaxNodes = D.LeafNodes[I].Node; for (int I = 0; I < D.NumCalls; ++I) if (static_cast(D.Calls[I].FromNode) > MaxNodes) MaxNodes = D.Calls[I].FromNode; // No nodes? Nothing to do if (MaxNodes < 0) { DEBUG(report("No nodes!\n")); CFGNodes = nullptr; SpanningTreeNodes = nullptr; NumNodes = 0; return; } ++MaxNodes; DEBUG(reportNumber("NumNodes = ", MaxNodes, 10)); NumNodes = static_cast(MaxNodes); // Initial allocations CFGNodes = new (Alloc) Node[MaxNodes]; DEBUG(reportNumber("G->CFGNodes = 0x", (uint64_t)CFGNodes, 16)); SpanningTreeNodes = new (Alloc) Node[MaxNodes]; DEBUG(reportNumber("G->SpanningTreeNodes = 0x", (uint64_t)SpanningTreeNodes, 16)); // Figure out how much to allocate to each vector (in/out edge sets) for (int I = 0; I < D.NumEdges; ++I) { CFGNodes[D.Edges[I].FromNode].NumOutEdges++; CFGNodes[D.Edges[I].ToNode].NumInEdges++; if (D.Edges[I].Counter != 0xffffffff) continue; SpanningTreeNodes[D.Edges[I].FromNode].NumOutEdges++; SpanningTreeNodes[D.Edges[I].ToNode].NumInEdges++; } // Allocate in/out edge sets for (int I = 0; I < MaxNodes; ++I) { if (CFGNodes[I].NumInEdges > 0) CFGNodes[I].InEdges = new (Alloc) Edge[CFGNodes[I].NumInEdges]; if (CFGNodes[I].NumOutEdges > 0) CFGNodes[I].OutEdges = new (Alloc) Edge[CFGNodes[I].NumOutEdges]; if (SpanningTreeNodes[I].NumInEdges > 0) SpanningTreeNodes[I].InEdges = new (Alloc) Edge[SpanningTreeNodes[I].NumInEdges]; if (SpanningTreeNodes[I].NumOutEdges > 0) SpanningTreeNodes[I].OutEdges = new (Alloc) Edge[SpanningTreeNodes[I].NumOutEdges]; CFGNodes[I].NumInEdges = 0; CFGNodes[I].NumOutEdges = 0; SpanningTreeNodes[I].NumInEdges = 0; SpanningTreeNodes[I].NumOutEdges = 0; } // Fill in/out edge sets for (int I = 0; I < D.NumEdges; ++I) { const uint32_t Src = D.Edges[I].FromNode; const uint32_t Dst = D.Edges[I].ToNode; Edge *E = &CFGNodes[Src].OutEdges[CFGNodes[Src].NumOutEdges++]; E->Node = Dst; E->ID = I; E = &CFGNodes[Dst].InEdges[CFGNodes[Dst].NumInEdges++]; E->Node = Src; E->ID = I; if (D.Edges[I].Counter != 0xffffffff) continue; E = &SpanningTreeNodes[Src] .OutEdges[SpanningTreeNodes[Src].NumOutEdges++]; E->Node = Dst; E->ID = I; E = &SpanningTreeNodes[Dst] .InEdges[SpanningTreeNodes[Dst].NumInEdges++]; E->Node = Src; E->ID = I; } computeEdgeFrequencies(Counters, Ctx); } Graph::~Graph() { if (CallFreqs) Alloc.deallocate(CallFreqs); if (EdgeFreqs) Alloc.deallocate(EdgeFreqs); for (int I = NumNodes - 1; I >= 0; --I) { if (SpanningTreeNodes[I].OutEdges) Alloc.deallocate(SpanningTreeNodes[I].OutEdges); if (SpanningTreeNodes[I].InEdges) Alloc.deallocate(SpanningTreeNodes[I].InEdges); if (CFGNodes[I].OutEdges) Alloc.deallocate(CFGNodes[I].OutEdges); if (CFGNodes[I].InEdges) Alloc.deallocate(CFGNodes[I].InEdges); } if (SpanningTreeNodes) Alloc.deallocate(SpanningTreeNodes); if (CFGNodes) Alloc.deallocate(CFGNodes); } void Graph::dump() const { reportNumber("Dumping graph with number of nodes: ", NumNodes, 10); report(" Full graph:\n"); for (int I = 0; I < NumNodes; ++I) { const Node *N = &CFGNodes[I]; reportNumber(" Node #", I, 10); reportNumber(" InEdges total ", N->NumInEdges, 10); for (int J = 0; J < N->NumInEdges; ++J) reportNumber(" ", N->InEdges[J].Node, 10); reportNumber(" OutEdges total ", N->NumOutEdges, 10); for (int J = 0; J < N->NumOutEdges; ++J) reportNumber(" ", N->OutEdges[J].Node, 10); report("\n"); } report(" Spanning tree:\n"); for (int I = 0; I < NumNodes; ++I) { const Node *N = &SpanningTreeNodes[I]; reportNumber(" Node #", I, 10); reportNumber(" InEdges total ", N->NumInEdges, 10); for (int J = 0; J < N->NumInEdges; ++J) reportNumber(" ", N->InEdges[J].Node, 10); reportNumber(" OutEdges total ", N->NumOutEdges, 10); for (int J = 0; J < N->NumOutEdges; ++J) reportNumber(" ", N->OutEdges[J].Node, 10); report("\n"); } } void Graph::dumpEdgeFreqs() const { reportNumber( "Dumping edge frequencies for graph with num edges: ", D.NumEdges, 10); for (int I = 0; I < D.NumEdges; ++I) { reportNumber("* Src: ", D.Edges[I].FromNode, 10); reportNumber(" Dst: ", D.Edges[I].ToNode, 10); reportNumber(" Cnt: ", EdgeFreqs[I], 10); } } /// Auxiliary map structure for fast lookups of which calls map to each node of /// the function CFG struct NodeToCallsMap { struct MapEntry { uint32_t NumCalls; uint32_t *Calls; }; MapEntry *Entries; BumpPtrAllocator &Alloc; const uint32_t NumNodes; NodeToCallsMap(BumpPtrAllocator &Alloc, const FunctionDescription &D, uint32_t NumNodes) : Alloc(Alloc), NumNodes(NumNodes) { Entries = new (Alloc, 0) MapEntry[NumNodes]; for (int I = 0; I < D.NumCalls; ++I) { DEBUG(reportNumber("Registering call in node ", D.Calls[I].FromNode, 10)); ++Entries[D.Calls[I].FromNode].NumCalls; } for (int I = 0; I < NumNodes; ++I) { Entries[I].Calls = Entries[I].NumCalls ? new (Alloc) uint32_t[Entries[I].NumCalls] : nullptr; Entries[I].NumCalls = 0; } for (int I = 0; I < D.NumCalls; ++I) { MapEntry &Entry = Entries[D.Calls[I].FromNode]; Entry.Calls[Entry.NumCalls++] = I; } } /// Set the frequency of all calls in node \p NodeID to Freq. However, if /// the calls have their own counters and do not depend on the basic block /// counter, this means they have landing pads and throw exceptions. In this /// case, set their frequency with their counters and return the maximum /// value observed in such counters. This will be used as the new frequency /// at basic block entry. This is used to fix the CFG edge frequencies in the /// presence of exceptions. uint64_t visitAllCallsIn(uint32_t NodeID, uint64_t Freq, uint64_t *CallFreqs, const FunctionDescription &D, const uint64_t *Counters, ProfileWriterContext &Ctx) const { const MapEntry &Entry = Entries[NodeID]; uint64_t MaxValue = 0ull; for (int I = 0, E = Entry.NumCalls; I != E; ++I) { const uint32_t CallID = Entry.Calls[I]; DEBUG(reportNumber(" Setting freq for call ID: ", CallID, 10)); const CallDescription &CallDesc = D.Calls[CallID]; if (CallDesc.Counter == 0xffffffff) { CallFreqs[CallID] = Freq; DEBUG(reportNumber(" with : ", Freq, 10)); } else { const uint64_t CounterVal = Counters[CallDesc.Counter]; CallFreqs[CallID] = CounterVal; MaxValue = CounterVal > MaxValue ? CounterVal : MaxValue; DEBUG(reportNumber(" with (private counter) : ", CounterVal, 10)); } DEBUG(reportNumber(" Address: 0x", CallDesc.TargetAddress, 16)); if (CallFreqs[CallID] > 0) Ctx.CallFlowTable->get(CallDesc.TargetAddress).Calls += CallFreqs[CallID]; } return MaxValue; } ~NodeToCallsMap() { for (int I = NumNodes - 1; I >= 0; --I) if (Entries[I].Calls) Alloc.deallocate(Entries[I].Calls); Alloc.deallocate(Entries); } }; /// Fill an array with the frequency of each edge in the function represented /// by G, as well as another array for each call. void Graph::computeEdgeFrequencies(const uint64_t *Counters, ProfileWriterContext &Ctx) { if (NumNodes == 0) return; EdgeFreqs = D.NumEdges ? new (Alloc, 0) uint64_t [D.NumEdges] : nullptr; CallFreqs = D.NumCalls ? new (Alloc, 0) uint64_t [D.NumCalls] : nullptr; // Setup a lookup for calls present in each node (BB) NodeToCallsMap *CallMap = new (Alloc) NodeToCallsMap(Alloc, D, NumNodes); // Perform a bottom-up, BFS traversal of the spanning tree in G. Edges in the // spanning tree don't have explicit counters. We must infer their value using // a linear combination of other counters (sum of counters of the outgoing // edges minus sum of counters of the incoming edges). uint32_t *Stack = new (Alloc) uint32_t [NumNodes]; uint32_t StackTop = 0; enum Status : uint8_t { S_NEW = 0, S_VISITING, S_VISITED }; Status *Visited = new (Alloc, 0) Status[NumNodes]; uint64_t *LeafFrequency = new (Alloc, 0) uint64_t[NumNodes]; uint64_t *EntryAddress = new (Alloc, 0) uint64_t[NumNodes]; // Setup a fast lookup for frequency of leaf nodes, which have special // basic block frequency instrumentation (they are not edge profiled). for (int I = 0; I < D.NumLeafNodes; ++I) { LeafFrequency[D.LeafNodes[I].Node] = Counters[D.LeafNodes[I].Counter]; DEBUG({ if (Counters[D.LeafNodes[I].Counter] > 0) { reportNumber("Leaf Node# ", D.LeafNodes[I].Node, 10); reportNumber(" Counter: ", Counters[D.LeafNodes[I].Counter], 10); } }); } for (int I = 0; I < D.NumEntryNodes; ++I) { EntryAddress[D.EntryNodes[I].Node] = D.EntryNodes[I].Address; DEBUG({ reportNumber("Entry Node# ", D.EntryNodes[I].Node, 10); reportNumber(" Address: ", D.EntryNodes[I].Address, 16); }); } // Add all root nodes to the stack for (int I = 0; I < NumNodes; ++I) if (SpanningTreeNodes[I].NumInEdges == 0) Stack[StackTop++] = I; // Empty stack? if (StackTop == 0) { DEBUG(report("Empty stack!\n")); Alloc.deallocate(EntryAddress); Alloc.deallocate(LeafFrequency); Alloc.deallocate(Visited); Alloc.deallocate(Stack); CallMap->~NodeToCallsMap(); Alloc.deallocate(CallMap); if (CallFreqs) Alloc.deallocate(CallFreqs); if (EdgeFreqs) Alloc.deallocate(EdgeFreqs); EdgeFreqs = nullptr; CallFreqs = nullptr; return; } // Add all known edge counts, will infer the rest for (int I = 0; I < D.NumEdges; ++I) { const uint32_t C = D.Edges[I].Counter; if (C == 0xffffffff) // inferred counter - we will compute its value continue; EdgeFreqs[I] = Counters[C]; } while (StackTop > 0) { const uint32_t Cur = Stack[--StackTop]; DEBUG({ if (Visited[Cur] == S_VISITING) report("(visiting) "); else report("(new) "); reportNumber("Cur: ", Cur, 10); }); // This shouldn't happen in a tree assert(Visited[Cur] != S_VISITED, "should not have visited nodes in stack"); if (Visited[Cur] == S_NEW) { Visited[Cur] = S_VISITING; Stack[StackTop++] = Cur; assert(StackTop <= NumNodes, "stack grew too large"); for (int I = 0, E = SpanningTreeNodes[Cur].NumOutEdges; I < E; ++I) { const uint32_t Succ = SpanningTreeNodes[Cur].OutEdges[I].Node; Stack[StackTop++] = Succ; assert(StackTop <= NumNodes, "stack grew too large"); } continue; } Visited[Cur] = S_VISITED; // Establish our node frequency based on outgoing edges, which should all be // resolved by now. int64_t CurNodeFreq = LeafFrequency[Cur]; // Not a leaf? if (!CurNodeFreq) { for (int I = 0, E = CFGNodes[Cur].NumOutEdges; I != E; ++I) { const uint32_t SuccEdge = CFGNodes[Cur].OutEdges[I].ID; CurNodeFreq += EdgeFreqs[SuccEdge]; } } if (CurNodeFreq < 0) CurNodeFreq = 0; const uint64_t CallFreq = CallMap->visitAllCallsIn( Cur, CurNodeFreq > 0 ? CurNodeFreq : 0, CallFreqs, D, Counters, Ctx); // Exception handling affected our output flow? Fix with calls info DEBUG({ if (CallFreq > CurNodeFreq) report("Bumping node frequency with call info\n"); }); CurNodeFreq = CallFreq > CurNodeFreq ? CallFreq : CurNodeFreq; if (CurNodeFreq > 0) { if (uint64_t Addr = EntryAddress[Cur]) { DEBUG( reportNumber(" Setting flow at entry point address 0x", Addr, 16)); DEBUG(reportNumber(" with: ", CurNodeFreq, 10)); Ctx.CallFlowTable->get(Addr).Val = CurNodeFreq; } } // No parent? Reached a tree root, limit to call frequency updating. if (SpanningTreeNodes[Cur].NumInEdges == 0) continue; assert(SpanningTreeNodes[Cur].NumInEdges == 1, "must have 1 parent"); const uint32_t ParentEdge = SpanningTreeNodes[Cur].InEdges[0].ID; // Calculate parent edge freq. int64_t ParentEdgeFreq = CurNodeFreq; for (int I = 0, E = CFGNodes[Cur].NumInEdges; I != E; ++I) { const uint32_t PredEdge = CFGNodes[Cur].InEdges[I].ID; ParentEdgeFreq -= EdgeFreqs[PredEdge]; } // Sometimes the conservative CFG that BOLT builds will lead to incorrect // flow computation. For example, in a BB that transitively calls the exit // syscall, BOLT will add a fall-through successor even though it should not // have any successors. So this block execution will likely be wrong. We // tolerate this imperfection since this case should be quite infrequent. if (ParentEdgeFreq < 0) { DEBUG(dumpEdgeFreqs()); DEBUG(report("WARNING: incorrect flow")); ParentEdgeFreq = 0; } DEBUG(reportNumber(" Setting freq for ParentEdge: ", ParentEdge, 10)); DEBUG(reportNumber(" with ParentEdgeFreq: ", ParentEdgeFreq, 10)); EdgeFreqs[ParentEdge] = ParentEdgeFreq; } Alloc.deallocate(EntryAddress); Alloc.deallocate(LeafFrequency); Alloc.deallocate(Visited); Alloc.deallocate(Stack); CallMap->~NodeToCallsMap(); Alloc.deallocate(CallMap); DEBUG(dumpEdgeFreqs()); } /// Write to \p FD all of the edge profiles for function \p FuncDesc. Uses /// \p Alloc to allocate helper dynamic structures used to compute profile for /// edges that we do not explicitly instrument. const uint8_t *writeFunctionProfile(int FD, ProfileWriterContext &Ctx, const uint8_t *FuncDesc, BumpPtrAllocator &Alloc) { const FunctionDescription F(FuncDesc); const uint8_t *next = FuncDesc + F.getSize(); #if !defined(__APPLE__) uint64_t *bolt_instr_locations = __bolt_instr_locations; #else uint64_t *bolt_instr_locations = _bolt_instr_locations_getter(); #endif // Skip funcs we know are cold #ifndef ENABLE_DEBUG uint64_t CountersFreq = 0; for (int I = 0; I < F.NumLeafNodes; ++I) CountersFreq += bolt_instr_locations[F.LeafNodes[I].Counter]; if (CountersFreq == 0) { for (int I = 0; I < F.NumEdges; ++I) { const uint32_t C = F.Edges[I].Counter; if (C == 0xffffffff) continue; CountersFreq += bolt_instr_locations[C]; } if (CountersFreq == 0) { for (int I = 0; I < F.NumCalls; ++I) { const uint32_t C = F.Calls[I].Counter; if (C == 0xffffffff) continue; CountersFreq += bolt_instr_locations[C]; } if (CountersFreq == 0) return next; } } #endif Graph *G = new (Alloc) Graph(Alloc, F, bolt_instr_locations, Ctx); DEBUG(G->dump()); if (!G->EdgeFreqs && !G->CallFreqs) { G->~Graph(); Alloc.deallocate(G); return next; } for (int I = 0; I < F.NumEdges; ++I) { const uint64_t Freq = G->EdgeFreqs[I]; if (Freq == 0) continue; const EdgeDescription *Desc = &F.Edges[I]; char LineBuf[BufSize]; char *Ptr = LineBuf; Ptr = serializeLoc(Ctx, Ptr, Desc->From, BufSize); Ptr = serializeLoc(Ctx, Ptr, Desc->To, BufSize - (Ptr - LineBuf)); Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 22); Ptr = intToStr(Ptr, Freq, 10); *Ptr++ = '\n'; __write(FD, LineBuf, Ptr - LineBuf); } for (int I = 0; I < F.NumCalls; ++I) { const uint64_t Freq = G->CallFreqs[I]; if (Freq == 0) continue; char LineBuf[BufSize]; char *Ptr = LineBuf; const CallDescription *Desc = &F.Calls[I]; Ptr = serializeLoc(Ctx, Ptr, Desc->From, BufSize); Ptr = serializeLoc(Ctx, Ptr, Desc->To, BufSize - (Ptr - LineBuf)); Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25); Ptr = intToStr(Ptr, Freq, 10); *Ptr++ = '\n'; __write(FD, LineBuf, Ptr - LineBuf); } G->~Graph(); Alloc.deallocate(G); return next; } #if !defined(__APPLE__) const IndCallTargetDescription * ProfileWriterContext::lookupIndCallTarget(uint64_t Target) const { uint32_t B = 0; uint32_t E = __bolt_instr_num_ind_targets; if (E == 0) return nullptr; do { uint32_t I = (E - B) / 2 + B; if (IndCallTargets[I].Address == Target) return &IndCallTargets[I]; if (IndCallTargets[I].Address < Target) B = I + 1; else E = I; } while (B < E); return nullptr; } /// Write a single indirect call pair to the fdata file void visitIndCallCounter(IndirectCallHashTable::MapEntry &Entry, int FD, int CallsiteID, ProfileWriterContext *Ctx) { if (Entry.Val == 0) return; DEBUG(reportNumber("Target func 0x", Entry.Key, 16)); DEBUG(reportNumber("Target freq: ", Entry.Val, 10)); const IndCallDescription *CallsiteDesc = &Ctx->IndCallDescriptions[CallsiteID]; const IndCallTargetDescription *TargetDesc = Ctx->lookupIndCallTarget(Entry.Key - TextBaseAddress); if (!TargetDesc) { DEBUG(report("Failed to lookup indirect call target\n")); char LineBuf[BufSize]; char *Ptr = LineBuf; Ptr = serializeLoc(*Ctx, Ptr, *CallsiteDesc, BufSize); Ptr = strCopy(Ptr, "0 [unknown] 0 0 ", BufSize - (Ptr - LineBuf) - 40); Ptr = intToStr(Ptr, Entry.Val, 10); *Ptr++ = '\n'; __write(FD, LineBuf, Ptr - LineBuf); return; } Ctx->CallFlowTable->get(TargetDesc->Address).Calls += Entry.Val; char LineBuf[BufSize]; char *Ptr = LineBuf; Ptr = serializeLoc(*Ctx, Ptr, *CallsiteDesc, BufSize); Ptr = serializeLoc(*Ctx, Ptr, TargetDesc->Loc, BufSize - (Ptr - LineBuf)); Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25); Ptr = intToStr(Ptr, Entry.Val, 10); *Ptr++ = '\n'; __write(FD, LineBuf, Ptr - LineBuf); } /// Write to \p FD all of the indirect call profiles. void writeIndirectCallProfile(int FD, ProfileWriterContext &Ctx) { for (int I = 0; I < __bolt_instr_num_ind_calls; ++I) { DEBUG(reportNumber("IndCallsite #", I, 10)); GlobalIndCallCounters[I].forEachElement(visitIndCallCounter, FD, I, &Ctx); } } /// Check a single call flow for a callee versus all known callers. If there are /// less callers than what the callee expects, write the difference with source /// [unknown] in the profile. void visitCallFlowEntry(CallFlowHashTable::MapEntry &Entry, int FD, ProfileWriterContext *Ctx) { DEBUG(reportNumber("Call flow entry address: 0x", Entry.Key, 16)); DEBUG(reportNumber("Calls: ", Entry.Calls, 10)); DEBUG(reportNumber("Reported entry frequency: ", Entry.Val, 10)); DEBUG({ if (Entry.Calls > Entry.Val) report(" More calls than expected!\n"); }); if (Entry.Val <= Entry.Calls) return; DEBUG(reportNumber( " Balancing calls with traffic: ", Entry.Val - Entry.Calls, 10)); const IndCallTargetDescription *TargetDesc = Ctx->lookupIndCallTarget(Entry.Key); if (!TargetDesc) { // There is probably something wrong with this callee and this should be // investigated, but I don't want to assert and lose all data collected. DEBUG(report("WARNING: failed to look up call target!\n")); return; } char LineBuf[BufSize]; char *Ptr = LineBuf; Ptr = strCopy(Ptr, "0 [unknown] 0 ", BufSize); Ptr = serializeLoc(*Ctx, Ptr, TargetDesc->Loc, BufSize - (Ptr - LineBuf)); Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25); Ptr = intToStr(Ptr, Entry.Val - Entry.Calls, 10); *Ptr++ = '\n'; __write(FD, LineBuf, Ptr - LineBuf); } /// Open fdata file for writing and return a valid file descriptor, aborting /// program upon failure. int openProfile() { // Build the profile name string by appending our PID char Buf[BufSize]; uint64_t PID = __getpid(); char *Ptr = strCopy(Buf, __bolt_instr_filename, BufSize); if (__bolt_instr_use_pid) { Ptr = strCopy(Ptr, ".", BufSize - (Ptr - Buf + 1)); Ptr = intToStr(Ptr, PID, 10); Ptr = strCopy(Ptr, ".fdata", BufSize - (Ptr - Buf + 1)); } *Ptr++ = '\0'; uint64_t FD = __open(Buf, O_WRONLY | O_TRUNC | O_CREAT, /*mode=*/0666); if (static_cast(FD) < 0) { report("Error while trying to open profile file for writing: "); report(Buf); reportNumber("\nFailed with error number: 0x", 0 - static_cast(FD), 16); __exit(1); } return FD; } #endif } // anonymous namespace #if !defined(__APPLE__) /// Reset all counters in case you want to start profiling a new phase of your /// program independently of prior phases. /// The address of this function is printed by BOLT and this can be called by /// any attached debugger during runtime. There is a useful oneliner for gdb: /// /// gdb -p $(pgrep -xo PROCESSNAME) -ex 'p ((void(*)())0xdeadbeef)()' \ /// -ex 'set confirm off' -ex quit /// /// Where 0xdeadbeef is this function address and PROCESSNAME your binary file /// name. extern "C" void __bolt_instr_clear_counters() { memset(reinterpret_cast(__bolt_instr_locations), 0, __bolt_num_counters * 8); for (int I = 0; I < __bolt_instr_num_ind_calls; ++I) GlobalIndCallCounters[I].resetCounters(); } /// This is the entry point for profile writing. /// There are three ways of getting here: /// /// * Program execution ended, finalization methods are running and BOLT /// hooked into FINI from your binary dynamic section; /// * You used the sleep timer option and during initialization we forked /// a separate process that will call this function periodically; /// * BOLT prints this function address so you can attach a debugger and /// call this function directly to get your profile written to disk /// on demand. /// extern "C" void __attribute((force_align_arg_pointer)) __bolt_instr_data_dump(int FD) { // Already dumping if (!GlobalWriteProfileMutex->acquire()) return; int ret = __lseek(FD, 0, SEEK_SET); assert(ret == 0, "Failed to lseek!"); ret = __ftruncate(FD, 0); assert(ret == 0, "Failed to ftruncate!"); BumpPtrAllocator HashAlloc; HashAlloc.setMaxSize(0x6400000); ProfileWriterContext Ctx = readDescriptions(); Ctx.CallFlowTable = new (HashAlloc, 0) CallFlowHashTable(HashAlloc); DEBUG(printStats(Ctx)); BumpPtrAllocator Alloc; Alloc.setMaxSize(0x6400000); const uint8_t *FuncDesc = Ctx.FuncDescriptions; for (int I = 0, E = __bolt_instr_num_funcs; I < E; ++I) { FuncDesc = writeFunctionProfile(FD, Ctx, FuncDesc, Alloc); Alloc.clear(); DEBUG(reportNumber("FuncDesc now: ", (uint64_t)FuncDesc, 16)); } assert(FuncDesc == (void *)Ctx.Strings, "FuncDesc ptr must be equal to stringtable"); writeIndirectCallProfile(FD, Ctx); Ctx.CallFlowTable->forEachElement(visitCallFlowEntry, FD, &Ctx); __fsync(FD); __munmap(Ctx.MMapPtr, Ctx.MMapSize); __close(Ctx.FileDesc); HashAlloc.destroy(); GlobalWriteProfileMutex->release(); DEBUG(report("Finished writing profile.\n")); } /// Event loop for our child process spawned during setup to dump profile data /// at user-specified intervals void watchProcess() { timespec ts, rem; uint64_t Ellapsed = 0ull; int FD = openProfile(); uint64_t ppid; if (__bolt_instr_wait_forks) { // Store parent pgid ppid = -__getpgid(0); // And leave parent process group __setpgid(0, 0); } else { // Store parent pid ppid = __getppid(); if (ppid == 1) { // Parent already dead __bolt_instr_data_dump(FD); goto out; } } ts.tv_sec = 1; ts.tv_nsec = 0; while (1) { __nanosleep(&ts, &rem); // This means our parent process or all its forks are dead, // so no need for us to keep dumping. if (__kill(ppid, 0) < 0) { if (__bolt_instr_no_counters_clear) __bolt_instr_data_dump(FD); break; } if (++Ellapsed < __bolt_instr_sleep_time) continue; Ellapsed = 0; __bolt_instr_data_dump(FD); if (__bolt_instr_no_counters_clear == false) __bolt_instr_clear_counters(); } out:; DEBUG(report("My parent process is dead, bye!\n")); __close(FD); __exit(0); } extern "C" void __bolt_instr_indirect_call(); extern "C" void __bolt_instr_indirect_tailcall(); /// Initialization code extern "C" void __attribute((force_align_arg_pointer)) __bolt_instr_setup() { __bolt_ind_call_counter_func_pointer = __bolt_instr_indirect_call; __bolt_ind_tailcall_counter_func_pointer = __bolt_instr_indirect_tailcall; TextBaseAddress = getTextBaseAddress(); const uint64_t CountersStart = reinterpret_cast(&__bolt_instr_locations[0]); const uint64_t CountersEnd = alignTo( reinterpret_cast(&__bolt_instr_locations[__bolt_num_counters]), 0x1000); DEBUG(reportNumber("replace mmap start: ", CountersStart, 16)); DEBUG(reportNumber("replace mmap stop: ", CountersEnd, 16)); assert(CountersEnd > CountersStart, "no counters"); const bool Shared = !__bolt_instr_use_pid; const uint64_t MapPrivateOrShared = Shared ? MAP_SHARED : MAP_PRIVATE; void *Ret = __mmap(CountersStart, CountersEnd - CountersStart, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MapPrivateOrShared | MAP_FIXED, -1, 0); assert(Ret != MAP_FAILED, "__bolt_instr_setup: Failed to mmap counters!"); GlobalMetadataStorage = __mmap(0, 4096, PROT_READ | PROT_WRITE, MapPrivateOrShared | MAP_ANONYMOUS, -1, 0); assert(GlobalMetadataStorage != MAP_FAILED, "__bolt_instr_setup: failed to mmap page for metadata!"); GlobalAlloc = new (GlobalMetadataStorage) BumpPtrAllocator; // Conservatively reserve 100MiB GlobalAlloc->setMaxSize(0x6400000); GlobalAlloc->setShared(Shared); GlobalWriteProfileMutex = new (*GlobalAlloc, 0) Mutex(); if (__bolt_instr_num_ind_calls > 0) GlobalIndCallCounters = new (*GlobalAlloc, 0) IndirectCallHashTable[__bolt_instr_num_ind_calls]; if (__bolt_instr_sleep_time != 0) { // Separate instrumented process to the own process group if (__bolt_instr_wait_forks) __setpgid(0, 0); if (long PID = __fork()) return; watchProcess(); } } extern "C" __attribute((force_align_arg_pointer)) void instrumentIndirectCall(uint64_t Target, uint64_t IndCallID) { GlobalIndCallCounters[IndCallID].incrementVal(Target, *GlobalAlloc); } /// We receive as in-stack arguments the identifier of the indirect call site /// as well as the target address for the call extern "C" __attribute((naked)) void __bolt_instr_indirect_call() { #if defined(__aarch64__) // clang-format off __asm__ __volatile__(SAVE_ALL "ldp x0, x1, [sp, #288]\n" "bl instrumentIndirectCall\n" RESTORE_ALL "ret\n" :::); // clang-format on #else // clang-format off __asm__ __volatile__(SAVE_ALL "mov 0xa0(%%rsp), %%rdi\n" "mov 0x98(%%rsp), %%rsi\n" "call instrumentIndirectCall\n" RESTORE_ALL "ret\n" :::); // clang-format on #endif } extern "C" __attribute((naked)) void __bolt_instr_indirect_tailcall() { #if defined(__aarch64__) // clang-format off __asm__ __volatile__(SAVE_ALL "ldp x0, x1, [sp, #288]\n" "bl instrumentIndirectCall\n" RESTORE_ALL "ret\n" :::); // clang-format on #else // clang-format off __asm__ __volatile__(SAVE_ALL "mov 0x98(%%rsp), %%rdi\n" "mov 0x90(%%rsp), %%rsi\n" "call instrumentIndirectCall\n" RESTORE_ALL "ret\n" :::); // clang-format on #endif } /// This is hooking ELF's entry, it needs to save all machine state. extern "C" __attribute((naked)) void __bolt_instr_start() { #if defined(__aarch64__) // clang-format off __asm__ __volatile__(SAVE_ALL "bl __bolt_instr_setup\n" RESTORE_ALL "adrp x16, __bolt_start_trampoline\n" "add x16, x16, #:lo12:__bolt_start_trampoline\n" "br x16\n" :::); // clang-format on #else // clang-format off __asm__ __volatile__(SAVE_ALL "call __bolt_instr_setup\n" RESTORE_ALL "jmp __bolt_start_trampoline\n" :::); // clang-format on #endif } /// This is hooking into ELF's DT_FINI extern "C" void __bolt_instr_fini() { #if defined(__aarch64__) // clang-format off __asm__ __volatile__(SAVE_ALL "adrp x16, __bolt_fini_trampoline\n" "add x16, x16, #:lo12:__bolt_fini_trampoline\n" "blr x16\n" RESTORE_ALL :::); // clang-format on #else __asm__ __volatile__("call __bolt_fini_trampoline\n" :::); #endif if (__bolt_instr_sleep_time == 0) { int FD = openProfile(); __bolt_instr_data_dump(FD); __close(FD); } DEBUG(report("Finished.\n")); } #endif #if defined(__APPLE__) extern "C" void __bolt_instr_data_dump() { ProfileWriterContext Ctx = readDescriptions(); int FD = 2; BumpPtrAllocator Alloc; const uint8_t *FuncDesc = Ctx.FuncDescriptions; uint32_t bolt_instr_num_funcs = _bolt_instr_num_funcs_getter(); for (int I = 0, E = bolt_instr_num_funcs; I < E; ++I) { FuncDesc = writeFunctionProfile(FD, Ctx, FuncDesc, Alloc); Alloc.clear(); DEBUG(reportNumber("FuncDesc now: ", (uint64_t)FuncDesc, 16)); } assert(FuncDesc == (void *)Ctx.Strings, "FuncDesc ptr must be equal to stringtable"); } // On OSX/iOS the final symbol name of an extern "C" function/variable contains // one extra leading underscore: _bolt_instr_setup -> __bolt_instr_setup. extern "C" __attribute__((section("__TEXT,__setup"))) __attribute__((force_align_arg_pointer)) void _bolt_instr_setup() { __asm__ __volatile__(SAVE_ALL :::); report("Hello!\n"); __asm__ __volatile__(RESTORE_ALL :::); } extern "C" __attribute__((section("__TEXT,__fini"))) __attribute__((force_align_arg_pointer)) void _bolt_instr_fini() { report("Bye!\n"); __bolt_instr_data_dump(); } #endif