[BOLT][Instrumentation] Fix indirect call profile in PIE

[treapster]

Summary

Proof-of-concept on how we may fix PIE indCall profile.
Here we create a getter for base address of .text and substract it's return value from recorded PC values. It converts them to static addresses, which then may be used to find the corresponding indirect call descriptions. The getter works by loading static address of __hot_end via leaq, then loading dynamic address via rip-relative leaq and returning the difference. I picked the end of text because it is the closest point of .text to the runtime library, which means it will almost certainly be within the reach of load instructions (important for future AArch64 support), and because __hot_end is easy to reuse.

[treapster]

While this works on our server, i get the following error on my x86_64 laptop:

FAILED: CMakeFiles/bolt_rt_instr_osx.dir/instr.cpp.o 
/usr/bin/clang++  -I/home/denis/randomshit/build/tools/bolt/bolt_rt-bins -O3 -DNDEBUG -std=c++17 -target x86_64-apple-darwin19.6.0 -ffreestanding -fno-exceptions -fno-rtti -fno-stack-protector -mno-sse -fPIC -MD -MT CMakeFiles/bolt_rt_instr_osx.dir/instr.cpp.o -MF CMakeFiles/bolt_rt_instr_osx.dir/instr.cpp.o.d -o CMakeFiles/bolt_rt_instr_osx.dir/instr.cpp.o -c /home/denis/randomshit/llvm-project/bolt/runtime/instr.cpp
In file included from /home/denis/randomshit/llvm-project/bolt/runtime/instr.cpp:44:
/home/denis/randomshit/llvm-project/bolt/runtime/common.h:146:48: error: 32-bit absolute addressing is not supported in 64-bit mode
  __asm__ volatile("leaq __hot_end(%%rip), %0\n\t"
                                               ^
<inline asm>:2:2: note: instantiated into assembly here
        leaq __hot_end, %rcx
        ^

I don't get why it says 32-bit addressing when leaq is 64-bit instruction? Changing it to movq makes no difference, but it definetely has something to do with OSX which i know nothing about.

[treapster]

Turns out, the cause of the issue was getBaseAddress() being in the extern "C" block(it wasn't on the server). Although i still don't get why it had such effect. Also, sorry for all the edits - i just tried to make underscores work in the diff description, but apparently there is no way without backticks.

[treapster]

Wait for profile in test - depends on D154436

[treapster]

Currently i cannot reproduce a failure which happens in CI

[treapster]

getBaseAddress -> getTextBaseAddress
Use movabsq to allow big addresses
Add a comment

[treapster]

Quote variables in bash

[treapster]

Add -fpie compiler flag
Hope it helps with failures

[treapster]

Change test to no-pie to check if PIE is the issue. If the failure persists, it must be bash script.
Unfortunately i can't reproduce it locally so i have to poke it in random places.

[treapster]

Changing test to no-pie made no difference. Now i replace wait_file calls with sleeps and if it passes, the script is definitely the issue. Even though i have no idea why.

[treapster]

Okay, this is stupid: it seems debian in CI just lacks fuser command, or it's not in path. I couldn't see the error because of stderr redirection to /dev/null. Here i add more return code checks and we should get an error that fuser is not found. What should we do next?

[treapster]

For now i just added fuser requirement to the test.

[treapster]

Gentle ping

[treapster]

• Use fuser -s instead of /dev/null redirection
• Fix wait_file.sh invoked with one extra argument

[treapster]

Pushed wrong patch last time

[treapster]

(once again) use -s flag with fuser

[treapster]

Ping

[rafauler]

Thanks! I can start looking into this next week (and the week after it) during my shift.

[treapster]

Ping

[rafauler]

Thanks for working on this. LGTM

bolt/lib/Rewrite/RewriteInstance.cpp

 
   if (!BC->HasRelocations &&
       opts::ReorderFunctions != ReorderFunctions::RT_NONE) {
     errs() << "BOLT-ERROR: function reordering only works when "
            << "relocations are enabled\n";
     exit(1);
   }
 
-  if (opts::ReorderFunctions != ReorderFunctions::RT_NONE &&
-      !opts::HotText.getNumOccurrences()) {
+  if (opts::Instrument ||
+      (opts::ReorderFunctions != ReorderFunctions::RT_NONE &&
+       !opts::HotText.getNumOccurrences())) {
     opts::HotText = true;
   } else if (opts::HotText && !BC->HasRelocations) {
     errs() << "BOLT-WARNING: hot text is disabled in non-relocation mode\n";
     opts::HotText = false;
   }
 
   if (opts::HotText && opts::HotTextMoveSections.getNumOccurrences() == 0) {
     opts::HotTextMoveSections.addValue(".stub");

bolt/runtime/common.h

int memcmp(const void *s1, const void *s2, size_t n) {
   }
   return 0;
 }
 } // extern "C"
 
 // Anonymous namespace covering everything but our library entry point
 namespace {
 
+// Get the difference between runtime addrress of .text section and
+// static address in section header table. Can be extracted from arbitrary
+// pc value recorded at runtime to get the corresponding static address, which
+// in turn can be used to search for indirect call description. Needed because
+// indirect call descriptions are read-only non-relocatable data.
+uint64_t getTextBaseAddress() {
+  uint64_t DynAddr;
+  uint64_t StaticAddr;
+  __asm__ volatile("leaq __hot_end(%%rip), %0\n\t"
+                   "movabsq $__hot_end, %1\n\t"
+                   : "=r"(DynAddr), "=r"(StaticAddr));
+  return DynAddr - StaticAddr;
+}
+
 constexpr uint32_t BufSize = 10240;
 
 #define _STRINGIFY(x) #x
 #define STRINGIFY(x) _STRINGIFY(x)
 
 uint64_t __read(uint64_t fd, const void *buf, uint64_t count) {
   uint64_t ret;
 #if defined(__APPLE__)

bolt/runtime/instr.cpp

private:
   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
void visitIndCallCounter(IndirectCallHashTable::MapEntry &Entry,
                          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);
+      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';

 
 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<uint64_t>(&__bolt_instr_locations[0]);
   const uint64_t CountersEnd = alignTo(
       reinterpret_cast<uint64_t>(&__bolt_instr_locations[__bolt_num_counters]),
       0x1000);
   DEBUG(reportNumber("replace mmap start: ", CountersStart, 16));
   DEBUG(reportNumber("replace mmap stop: ", CountersEnd, 16));

bolt/test/lit.cfg.py

else:
     )
 
 if config.bolt_enable_runtime:
     config.available_features.add("bolt-runtime")
 
 if config.gnu_ld:
     config.available_features.add("gnu_ld")
 
+if lit.util.which("fuser"):
+    config.available_features.add("fuser")
+
 llvm_config.use_default_substitutions()
 
 llvm_config.config.environment["CLANG"] = config.bolt_clang
 llvm_config.use_clang()
 
 llvm_config.config.environment["LD_LLD"] = config.bolt_lld
 ld_lld = llvm_config.use_llvm_tool("ld.lld", required=True, search_env="LD_LLD")
 llvm_config.config.available_features.add("ld.lld")

bolt/test/runtime/instrumentation-indirect-2.c

+// Check that indirect call hash tables properly register multiple calls,
+// and that calls from different processes don't get mixed up when using
+// --instrumentation-file-append-pid.
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+__attribute__((noinline)) void funcA(int pid) { printf("funcA %d\n", pid); }
+__attribute__((noinline)) void funcB(int pid) { printf("funcB %d\n", pid); }
+__attribute__((noinline)) void funcC(int pid) { printf("funcC %d\n", pid); }
+__attribute__((noinline)) void funcD(int pid) { printf("funcD %d\n", pid); }
+__attribute__((noinline)) void funcE(int pid) { printf("funcE %d\n", pid); }
+__attribute__((noinline)) void funcF(int pid) { printf("funcF %d\n", pid); }
+__attribute__((noinline)) void funcG(int pid) { printf("funcG %d\n", pid); }
+__attribute__((noinline)) void funcH(int pid) { printf("funcH %d\n", pid); }
+__attribute__((noinline)) void funcI(int pid) { printf("funcI %d\n", pid); }
+__attribute__((noinline)) void funcJ(int pid) { printf("funcJ %d\n", pid); }
+__attribute__((noinline)) void funcK(int pid) { printf("funcK %d\n", pid); }
+__attribute__((noinline)) void funcL(int pid) { printf("funcL %d\n", pid); }
+__attribute__((noinline)) void funcM(int pid) { printf("funcM %d\n", pid); }
+__attribute__((noinline)) void funcN(int pid) { printf("funcN %d\n", pid); }
+__attribute__((noinline)) void funcO(int pid) { printf("funcO %d\n", pid); }
+__attribute__((noinline)) void funcP(int pid) { printf("funcP %d\n", pid); }
+
+int main() {
+
+  void (*funcs[])(int) = {funcA, funcB, funcC, funcD, funcE, funcF,
+                          funcG, funcH, funcI, funcJ, funcK, funcL,
+                          funcM, funcN, funcO, funcP};
+  int i;
+
+  switch (fork()) {
+  case -1:
+    printf("Failed to fork!\n");
+    exit(-1);
+    break;
+  case 0:
+    i = 0;
+    break;
+  default:
+    i = 1;
+    break;
+  }
+  int pid = getpid();
+  for (; i < sizeof(funcs) / sizeof(void *); i += 2) {
+    funcs[i](pid);
+  }
+
+  return 0;
+}
+/*
+REQUIRES: system-linux,shell,fuser
+
+RUN: %clang %cflags %s -o %t.exe -Wl,-q -pie -fpie
+
+RUN: llvm-bolt %t.exe --instrument --instrumentation-file=%t.fdata \
+RUN:   --conservative-instrumentation -o %t.instrumented_conservative \
+RUN: --instrumentation-sleep-time=1 --instrumentation-no-counters-clear \
+RUN: --instrumentation-wait-forks
+
+# Instrumented program needs to finish returning zero
+# Both output and profile must contain all 16 functions
+RUN: %t.instrumented_conservative > %t.output
+# Wait for profile and output to be fully written
+RUN: bash %S/wait_file.sh %t.output
+RUN: bash %S/wait_file.sh %t.fdata
+RUN: cat %t.output | FileCheck %s --check-prefix=CHECK-OUTPUT
+RUN: cat %t.fdata | FileCheck %s --check-prefix=CHECK-COMMON-PROF
+
+CHECK-OUTPUT-DAG: funcA
+CHECK-OUTPUT-DAG: funcB
+CHECK-OUTPUT-DAG: funcC
+CHECK-OUTPUT-DAG: funcD
+CHECK-OUTPUT-DAG: funcE
+CHECK-OUTPUT-DAG: funcF
+CHECK-OUTPUT-DAG: funcG
+CHECK-OUTPUT-DAG: funcH
+CHECK-OUTPUT-DAG: funcI
+CHECK-OUTPUT-DAG: funcJ
+CHECK-OUTPUT-DAG: funcK
+CHECK-OUTPUT-DAG: funcL
+CHECK-OUTPUT-DAG: funcM
+CHECK-OUTPUT-DAG: funcN
+CHECK-OUTPUT-DAG: funcO
+CHECK-OUTPUT-DAG: funcP
+
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcA 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcB 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcC 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcD 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcE 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcF 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcG 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcH 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcI 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcJ 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcK 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcL 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcM 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcN 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcO 0 0 1
+CHECK-COMMON-PROF-DAG: 1 main {{[0-9a-f]+}} 1 funcP 0 0 1
+
+RUN: llvm-bolt %t.exe --instrument --instrumentation-file=%t \
+RUN:   --instrumentation-file-append-pid \
+RUN:   -o %t.instrumented
+
+RUN: %t.instrumented > %t.output
+# Wait till output is fully written in case child outlives parent
+RUN: bash %S/wait_file.sh %t.output
+# Make sure all functions were called
+RUN: cat %t.output | FileCheck %s --check-prefix=CHECK-OUTPUT
+
+RUN: child_pid=$(cat %t.output | grep funcA | awk '{print $2;}')
+RUN: par_pid=$(cat %t.output | grep funcB | awk '{print $2;}')
+
+RUN: bash %S/wait_file.sh %t.$child_pid.fdata
+RUN: bash %S/wait_file.sh %t.$par_pid.fdata
+
+RUN: mv %t.$child_pid.fdata %t.child.fdata
+RUN: mv %t.$par_pid.fdata %t.parent.fdata
+
+# Instrumented binary must produce two profiles with only local calls
+# recorded. Functions called only in child should not appear in parent's
+# process and vice versa.
+RUN: cat %t.child.fdata | FileCheck %s --check-prefix=CHECK-CHILD
+RUN: cat %t.child.fdata | FileCheck %s --check-prefix=CHECK-NOCHILD
+RUN: cat %t.parent.fdata | FileCheck %s --check-prefix=CHECK-PARENT
+RUN: cat %t.parent.fdata | FileCheck %s --check-prefix=CHECK-NOPARENT
+
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcA 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcC 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcE 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcG 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcI 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcK 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcM 0 0 1
+CHECK-CHILD-DAG: 1 main {{[0-9a-f]+}} 1 funcO 0 0 1
+
+CHECK-NOCHILD-NOT: funcB
+CHECK-NOCHILD-NOT: funcD
+CHECK-NOCHILD-NOT: funcF
+CHECK-NOCHILD-NOT: funcH
+CHECK-NOCHILD-NOT: funcJ
+CHECK-NOCHILD-NOT: funcL
+CHECK-NOCHILD-NOT: funcN
+CHECK-NOCHILD-NOT: funcP
+
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcB 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcD 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcF 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcH 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcJ 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcL 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcN 0 0 1
+CHECK-PARENT-DAG: 1 main {{[0-9a-f]+}} 1 funcP 0 0 1
+
+CHECK-NOPARENT-NOT: funcA
+CHECK-NOPARENT-NOT: funcC
+CHECK-NOPARENT-NOT: funcE
+CHECK-NOPARENT-NOT: funcG
+CHECK-NOPARENT-NOT: funcI
+CHECK-NOPARENT-NOT: funcK
+CHECK-NOPARENT-NOT: funcM
+CHECK-NOPARENT-NOT: funcO
+
+ */

bolt/test/runtime/wait_file.sh

+#!/bin/bash
+
+check_file() {
+    local file="$1"
+    if [ -z "$file" ]; then
+        echo "No file passed!"
+        exit 1
+    fi
+    if [ ! -f "$file" ]; then
+        return 1
+    fi
+
+    fuser "$file"
+    local ret=$?
+    if [ $ret -eq 1 ]; then # noone has file open
+        return 0
+    fi
+    if [ $ret -eq 0 ]; then # file open by some processes
+        return 1
+    fi
+    if [ $ret -eq 127 ]; then
+        echo "fuser command not found!"
+        exit 1
+    fi
+
+    echo "Unexpected exit code $ret from fuser!"
+    exit 1
+}
+
+wait_file() {
+    local file="$1"
+    local max_sleep=10
+    check_file "$file"
+    local ret=$?
+    while [ $ret -ne 0 ] && [ $max_sleep -ne 0 ]; do
+        sleep 1
+        max_sleep=$((max_sleep - 1))
+        check_file $file
+        ret=$?
+    done
+    if [ $max_sleep -eq 0 ]; then
+        echo "The file does not exist or the test hung!"
+        exit 1
+    fi
+
+}
+file="$1"
+wait_file "$file"