[BOLT][AArch64] Fix instrumentation deadloop

[yota9]

Summary

According to ARMv8-a architecture reference manual B2.10.5 software
must avoid having any explicit memory accesses between exclusive load
and associated store instruction. Otherwise exclusive monitor might
clear the exclusivity without application-related cause which may
result in the deadloop. Disable instrumentation for such functions,
since between exclusive load and store there might be branches and we
would insert instrumentation snippet which contains loads and stores.

The better solution would be to analyze with BFS finding the exact BBs
between load and store and not instrumenting them. Or even better to
recognize such sequences and replace them with more complex one, e.g.
loading value non exclusively, and for the brach where exclusive store
is made make exclusive load and store sequentially, but for now just
disable instrumentation for such functions completely.

[kristof.beyls]

Thank you for this patch!

One very minor comment: in the commit message, you refer to section E2.10.5 of the ArmARM. That section covers Load-Exclusive and Store-Exclusive instructions in AArch32 mode.
This patch targets AArch64. The corresponding section (for AArch64) in the ArmARM seems to be "B2.9.5 Load-Exclusive and Store-Exclusive instruction usage restrictions".

bolt/lib/Passes/Instrumentation.cpp

313

I'm afraid I'm not familiar with the instrumentation feature of BOLT.

Given that typically there are only few instructions (and as you write above, no memory-accessing instructions) in between a load-exclusive and a store-exclusive, I would expect that it should be possible to make most instrumentation work well, even in functions with load-exclusives and store-exclusives?

Maybe only instrumentation that tracks direct conditional branches may be affected?
And even then, maybe it wouldn't be too hard to identify the conditional branches that are between a load-exclusive and a store-exclusive and only stop instrumenting those conditional branches, but still instrument the other conditional branches in the function?

Anyway, to me it feels like that's an improvement that could be done in a follow-on patch?

If all of the above text seems sensible, maybe it would be best to add a "FIXME" comment here to indicate that with a bit more work most instrumentations in functions with load-exclusives/store-exclusives could still be made to work?

bolt/lib/Target/AArch64/AArch64MCPlusBuilder.cpp

292

It seems the following opcodes are missing?

LDAXPW, LDAXPX, LDXPW, LDXPX,
STLXPW, STLXPX, STXPW, STXPX.

[yota9]

Thank you for your review, Kristof! My bad, you're right, at my document it is B2.10.5 (Load-Exclusive and Store-Exclusive instruction usage restrictions), I would fix it in commit message.

bolt/lib/Passes/Instrumentation.cpp

313

I would add FIXME as you suggested.
As for the BOLT we're using multiple load/store instruction, e.g. to preserve the register values that we're using in snippets and for the atomic add for the execution counter. So every snippet would have load or store anyway

bolt/lib/Target/AArch64/AArch64MCPlusBuilder.cpp

292

Forgot about pair ones, thanks!

[yota9]

Address comments

[yota9]

nit

[yota9]

fix typo

[kristof.beyls]

Thank you, I don't have further comments.
I'm not up to speed enough on BOLT to be able to approve this patch, that will need to be done by one of the other reviewers.

[yota9]

Gentle ping @rafauler @maksfb

[Amir]

bolt/include/bolt/Core/MCPlusBuilder.h

629

"Exclusive" is ARM-specific term, so it would help to either clarify it a bit here, or come up with a generic term – maybe "isLoadLockStoreConditionalInst"?

bolt/lib/Passes/Instrumentation.cpp

315

Can you please factor out the check into a helper function e.g. hasExclusiveMemop?

[yota9]

bolt/include/bolt/Core/MCPlusBuilder.h

629

I agree. But we have a bunch of arch-specific interfaces, e.g. is adrp, islea, isRISCVCall. Usually I'm not insisting on such questions, but to my taste "isLoadLockStoreConditionalInst" is a little bit too complicated :)) I like the current variant to be honest, but maybe isAArch64Exclusive is good-enough compromise and in the future add isArch prefix for arch-specific things?

[yota9]

Move exlusive check to separate function.

Gentle ping @Amir @rafauler @maksfb

[Amir]

bolt/include/bolt/Core/MCPlusBuilder.h

629

Yes, isAArch64Exclusive is a good compromise.

bolt/lib/Passes/Instrumentation.cpp

310–311

[yota9]

address comments

[yota9]

clang-format

[yota9]

If no further comments, @Amir please approve. Thanks

[Amir]

Thanks!

bolt/include/bolt/Core/MCPlusBuilder.h

public:
   virtual bool mayLoad(const MCInst &Inst) const {
     return Info->get(Inst.getOpcode()).mayLoad();
   }
 
   virtual bool mayStore(const MCInst &Inst) const {
     return Info->get(Inst.getOpcode()).mayStore();
   }
 
+  virtual bool isAArch64Exclusive(const MCInst &Inst) const {
+    llvm_unreachable("not implemented");
+    return false;
+  }
+
   virtual bool isCleanRegXOR(const MCInst &Inst) const {
     llvm_unreachable("not implemented");
     return false;
   }
 
   virtual bool isPacked(const MCInst &Inst) const {
     llvm_unreachable("not implemented");
     return false;

bolt/lib/Passes/Instrumentation.cpp

 //===- bolt/Passes/Instrumentation.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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Instrumentation class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/Instrumentation.h"
 #include "bolt/Core/ParallelUtilities.h"
 #include "bolt/RuntimeLibs/InstrumentationRuntimeLibrary.h"
+#include "bolt/Utils/CommandLineOpts.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/RWMutex.h"
 #include <stack>
 
 #define DEBUG_TYPE "bolt-instrumentation"
 
 using namespace llvm;
cl::opt<bool> InstrumentCalls("instrument-calls",
                                        "control flow activity (default: true)"),
                               cl::init(true), cl::Optional,
                               cl::cat(BoltInstrCategory));
 } // namespace opts
 
 namespace llvm {
 namespace bolt {
 
+static bool hasAArch64ExclusiveMemop(BinaryFunction &Function) {
+  // FIXME ARMv8-a architecture reference manual says that software must avoid
+  // having any explicit memory accesses between exclusive load and associated
+  // store instruction. So for now skip instrumentation for functions that have
+  // these instructions, since it might lead to runtime deadlock.
+  BinaryContext &BC = Function.getBinaryContext();
+  for (const BinaryBasicBlock &BB : Function)
+    for (const MCInst &Inst : BB)
+      if (BC.MIB->isAArch64Exclusive(Inst)) {
+        if (opts::Verbosity >= 1)
+          outs() << "BOLT-INSTRUMENTER: Function " << Function
+                 << " has exclusive instructions, skip instrumentation\n";
+        return true;
+      }
+
+  return false;
+}
+
 uint32_t Instrumentation::getFunctionNameIndex(const BinaryFunction &Function) {
   auto Iter = FuncToStringIdx.find(&Function);
   if (Iter != FuncToStringIdx.end())
     return Iter->second;
   size_t Idx = Summary->StringTable.size();
   FuncToStringIdx.emplace(std::make_pair(&Function, Idx));
   Summary->StringTable.append(getEscapedName(Function.getOneName()));
   Summary->StringTable.append(1, '\0');
void Instrumentation::instrumentFunction(BinaryFunction &Function,
                                          MCPlusBuilder::AllocatorIdTy AllocId) {
   if (Function.hasUnknownControlFlow())
     return;
 
   BinaryContext &BC = Function.getBinaryContext();
   if (BC.isMachO() && Function.hasName("___GLOBAL_init_65535/1"))
     return;
 
+  if (BC.isAArch64() && hasAArch64ExclusiveMemop(Function))
+    return;
+
   SplitWorklistTy SplitWorklist;
   SplitInstrsTy SplitInstrs;
 
   FunctionDescription *FuncDesc = nullptr;
   {
     std::unique_lock<llvm::sys::RWMutex> L(FDMutex);
     Summary->FunctionDescriptions.emplace_back();
     FuncDesc = &Summary->FunctionDescriptions.back();
   }
 
   FuncDesc->Function = &Function;

bolt/lib/Target/AArch64/AArch64MCPlusBuilder.cpp

return (Inst.getOpcode() == AArch64::LDRXpost ||
             Inst.getOpcode() == AArch64::LDRXroX ||
             Inst.getOpcode() == AArch64::LDRXui);
   }
 
   bool mayLoad(const MCInst &Inst) const override {
     return isLDRB(Inst) || isLDRH(Inst) || isLDRW(Inst) || isLDRX(Inst);
   }
 
+  bool isAArch64Exclusive(const MCInst &Inst) const override {
+    return (Inst.getOpcode() == AArch64::LDXPX ||
+            Inst.getOpcode() == AArch64::LDXPW ||
+            Inst.getOpcode() == AArch64::LDXRX ||
+            Inst.getOpcode() == AArch64::LDXRW ||
+            Inst.getOpcode() == AArch64::LDXRH ||
+            Inst.getOpcode() == AArch64::LDXRB ||
+            Inst.getOpcode() == AArch64::STXPX ||
+            Inst.getOpcode() == AArch64::STXPW ||
+            Inst.getOpcode() == AArch64::STXRX ||
+            Inst.getOpcode() == AArch64::STXRW ||
+            Inst.getOpcode() == AArch64::STXRH ||
+            Inst.getOpcode() == AArch64::STXRB ||
+            Inst.getOpcode() == AArch64::LDAXPX ||
+            Inst.getOpcode() == AArch64::LDAXPW ||
+            Inst.getOpcode() == AArch64::LDAXRX ||
+            Inst.getOpcode() == AArch64::LDAXRW ||
+            Inst.getOpcode() == AArch64::LDAXRH ||
+            Inst.getOpcode() == AArch64::LDAXRB ||
+            Inst.getOpcode() == AArch64::STLXPX ||
+            Inst.getOpcode() == AArch64::STLXPW ||
+            Inst.getOpcode() == AArch64::STLXRX ||
+            Inst.getOpcode() == AArch64::STLXRW ||
+            Inst.getOpcode() == AArch64::STLXRH ||
+            Inst.getOpcode() == AArch64::STLXRB ||
+            Inst.getOpcode() == AArch64::CLREX);
+  }
+
   bool isLoadFromStack(const MCInst &Inst) const {
     if (!mayLoad(Inst))
       return false;
     for (const MCOperand &Operand : useOperands(Inst)) {
       if (!Operand.isReg())
         continue;
       unsigned Reg = Operand.getReg();
       if (Reg == AArch64::SP || Reg == AArch64::WSP || Reg == AArch64::FP ||

bolt/test/AArch64/exclusive-instrument.s

+// This test checks that the foo function having exclusive memory access
+// instructions won't be instrumented.
+
+// REQUIRES: system-linux,bolt-runtime,target=aarch64{{.*}}
+
+// RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown \
+// RUN:   %s -o %t.o
+// RUN: %clang %cflags -fPIC -pie %t.o -o %t.exe -nostdlib -Wl,-q -Wl,-fini=dummy
+// RUN: llvm-bolt %t.exe -o %t.bolt -instrument -v=1 | FileCheck %s
+
+// CHECK: Function foo has exclusive instructions, skip instrumentation
+
+.global foo
+.type foo, %function
+foo:
+  ldaxr w9, [x10]
+  cbnz w9, .Lret
+  stlxr w12, w11, [x9]
+  cbz w12, foo
+  clrex
+.Lret:
+  ret
+.size foo, .-foo
+
+.global _start
+.type _start, %function
+_start:
+  cmp x0, #0
+  b.eq .Lexit
+  bl foo
+.Lexit:
+  ret
+.size _start, .-_start
+
+.global dummy
+.type dummy, %function
+dummy:
+  ret
+.size dummy, .-dummy