[MSAN] Instrument libatomic load/store calls

[guiand]

Summary

These calls are neither intercepted by compiler-rt nor is libatomic.a
naturally instrumented.

This patch uses the existing libcall mechanism to detect a call
to atomic_load or atomic_store, and instruments them much like
the preexisting instrumentation for atomics.

Calls to _load are modified to have at least Acquire ordering, and
calls to _store at least Release ordering. Because this needs to be
converted at runtime, msan injects a LUT (implemented as a vector
with extractelement).

[guiand]

compiler-rt/test/msan/libatomic.c

38

One thing that turned out a little strange is that because I have to insert instructions *after* the atomic load, including the origin update, the msan reporter decides that the origin is one line below the call. Is there anything I can do about this?

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

1790

Is there a more elegant way to do this?

3462

Is it valid to assume any alignment other than 1 here? I can't think of a way, but I'd like to make sure.

[guiand]

Update TargetLibraryInfoTest to include new LibFunc declarations.

[vitalybuka]

llvm/include/llvm/Analysis/TargetLibraryInfo.def

266 ↗

(On Diff #276186)

Can you move TargetLibraryInfo extension into a separate patch

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

3462

Can we do MemCpy of shadow here at all? not all bits of shadow bytes correspond to the src/dst

3464

I'd use ", Align(1), " without temp var

3471

DstShadowPtr.first for consistency

[eugenis]

compiler-rt/test/msan/libatomic.c

38

use SetCurrentDebugLocation on the builder

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

3468

I think isStore needs to be true here.

3472

How about we do the same thing that happens to memcpy() calls in the user code, i.e. emit a call to __msan_memcpy?
It will take care of everything.

[guiand]

Split off the TLI changes to https://reviews.llvm.org/D83361

[guiand]

Addressed comments

[guiand]

isStore=true on atomic load destination

[eugenis]

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

3449

Check that the arguments are initialized (see ClCheckAccessAddress).

3477

Why not storeOrigin? It even has an option to use a runtime helper, a better one (conditional).

3503

Origin is meaningless when the shadow is 0.

[guiand]

Remove origin store from atomic_store

[guiand]

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

3477

Since this function isn't necessarily called with a constant size, I needed some way to set the origin for a variable-sized region too. It seems like storeOrigin and the maybe-store functions use constant sizes?

[eugenis]

LGTM

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

3477

Oh, right. OK, this should be good enough.

[eugenis]

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

3461

CB can be a terminator and not have a next node.
Example:

invoke void @__atomic_load(i64 48, i8* %4, i8* %5, i32 %6)
        to label %invoke.cont unwind label %terminate.lpad

This will crash in

#0  llvm::Value::getContext (this=0x0) at /code/llvm-project/llvm/lib/IR/Value.cpp:839
#1  0x0000000003e55767 in llvm::IRBuilder<llvm::ConstantFolder, llvm::IRBuilderDefaultInserter>::IRBuilder (
    this=0x7fffffffb4b0, IP=0x0, FPMathTag=0x0, OpBundles=...) at /code/llvm-project/llvm/include/llvm/IR/IRBuilder.h:2598
#2  0x00000000067e1233 in (anonymous namespace)::MemorySanitizerVisitor::visitLibAtomicLoad (this=0x7fffffffbfc0, CB=...)
    at /code/llvm-project/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp:3508
#3  0x00000000067dfd8d in (anonymous namespace)::MemorySanitizerVisitor::visitCallBase (this=0x7fffffffbfc0, CB=...)
    at /code/llvm-project/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp:3570
#4  0x00000000067dfc13 in llvm::InstVisitor<(anonymous namespace)::MemorySanitizerVisitor, void>::visitInvokeInst (
    this=0x7fffffffbfc0, I=...) at /code/llvm-project/llvm/include/llvm/IR/InstVisitor.h:220
#5  0x00000000067ddb40 in llvm::InstVisitor<(anonymous namespace)::MemorySanitizerVisitor, void>::visitInvoke (
    this=0x7fffffffbfc0, I=...) at /code/llvm-project/llvm/include/llvm/IR/Instruction.def:131

compiler-rt/test/msan/libatomic.c

+// RUN: %clangxx_msan -fsanitize-memory-track-origins=2 -latomic -DTEST_STORE -O0 %s -o %t && %run %t 2>&1
+// RUN: %clangxx_msan -fsanitize-memory-track-origins=0 -latomic -DTEST_LOAD -O0 %s -o %t && not %run %t 2>&1 | FileCheck %s --check-prefix=CHECK
+// RUN: %clangxx_msan -fsanitize-memory-track-origins=2 -latomic -DTEST_LOAD -O0 %s -o %t && not %run %t 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-SHADOW
+
+#include <sanitizer/msan_interface.h>
+#include <stdatomic.h>
+
+typedef struct __attribute((packed)) {
+  uint8_t val[3];
+} i24;
+
+void copy(i24 *dst, i24 *src);
+
+int main() {
+  i24 uninit;
+  i24 init = {0};
+
+  __msan_check_mem_is_initialized(&init, 3);
+  copy(&init, &uninit);
+  __msan_check_mem_is_initialized(&init, 3);
+}
+
+void copy(i24 *dst, i24 *src) {
+#ifdef TEST_LOAD
+  __atomic_load(src, dst, __ATOMIC_RELAXED);
+
+  // CHECK: MemorySanitizer: use-of-uninitialized-value
+  // CHECK: #0 {{0x[a-f0-9]+}} in main{{.*}}libatomic.c:[[@LINE-8]]
+
+  // CHECK-SHADOW: Uninitialized value was stored to memory at
+  // CHECK-SHADOW: #0 {{0x[a-f0-9]+}} in copy{{.*}}libatomic.c:[[@LINE-6]]
+#endif
+#ifdef TEST_STORE
+  // Store always writes a clean shadow
+  __atomic_store(src, dst, __ATOMIC_RELAXED);
+#endif
+}

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

private:
 
   /// Run-time helper that poisons stack on function entry.
   FunctionCallee MsanPoisonStackFn;
 
   /// Run-time helper that records a store (or any event) of an
   /// uninitialized value and returns an updated origin id encoding this info.
   FunctionCallee MsanChainOriginFn;
 
+  /// Run-time helper that paints an origin over a region.
+  FunctionCallee MsanSetOriginFn;
+
   /// MSan runtime replacements for memmove, memcpy and memset.
   FunctionCallee MemmoveFn, MemcpyFn, MemsetFn;
 
   /// KMSAN callback for task-local function argument shadow.
   StructType *MsanContextStateTy;
   FunctionCallee MsanGetContextStateFn;
 
   /// Functions for poisoning/unpoisoning local variables
void MemorySanitizer::initializeCallbacks(Module &M) {
   if (CallbacksInitialized)
     return;
 
   IRBuilder<> IRB(*C);
   // Initialize callbacks that are common for kernel and userspace
   // instrumentation.
   MsanChainOriginFn = M.getOrInsertFunction(
     "__msan_chain_origin", IRB.getInt32Ty(), IRB.getInt32Ty());
+  MsanSetOriginFn =
+      M.getOrInsertFunction("__msan_set_origin", IRB.getVoidTy(),
+                            IRB.getInt8PtrTy(), IntptrTy, IRB.getInt32Ty());
   MemmoveFn = M.getOrInsertFunction(
     "__msan_memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
     IRB.getInt8PtrTy(), IntptrTy);
   MemcpyFn = M.getOrInsertFunction(
     "__msan_memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
     IntptrTy);
   MemsetFn = M.getOrInsertFunction(
     "__msan_memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt32Ty(),
switch (a) {
       case AtomicOrdering::AcquireRelease:
         return AtomicOrdering::AcquireRelease;
       case AtomicOrdering::SequentiallyConsistent:
         return AtomicOrdering::SequentiallyConsistent;
     }
     llvm_unreachable("Unknown ordering");
   }
 
+  Value *makeAddReleaseOrderingTable(IRBuilder<> &IRB) {
+    constexpr int NumOrderings = (int)AtomicOrderingCABI::seq_cst + 1;
+    uint32_t OrderingTable[NumOrderings] = {};
+
+    OrderingTable[(int)AtomicOrderingCABI::relaxed] =
+        OrderingTable[(int)AtomicOrderingCABI::release] =
+            (int)AtomicOrderingCABI::release;
+    OrderingTable[(int)AtomicOrderingCABI::consume] =
+        OrderingTable[(int)AtomicOrderingCABI::acquire] =
+            OrderingTable[(int)AtomicOrderingCABI::acq_rel] =
+                (int)AtomicOrderingCABI::acq_rel;
+    OrderingTable[(int)AtomicOrderingCABI::seq_cst] =
+        (int)AtomicOrderingCABI::seq_cst;
+
+    return ConstantDataVector::get(IRB.getContext(),
+                                   makeArrayRef(OrderingTable, NumOrderings));
+  }
+
   AtomicOrdering addAcquireOrdering(AtomicOrdering a) {
     switch (a) {
       case AtomicOrdering::NotAtomic:
         return AtomicOrdering::NotAtomic;
       case AtomicOrdering::Unordered:
       case AtomicOrdering::Monotonic:
       case AtomicOrdering::Acquire:
         return AtomicOrdering::Acquire;
       case AtomicOrdering::Release:
       case AtomicOrdering::AcquireRelease:
         return AtomicOrdering::AcquireRelease;
       case AtomicOrdering::SequentiallyConsistent:
         return AtomicOrdering::SequentiallyConsistent;
     }
     llvm_unreachable("Unknown ordering");
   }
 
+  Value *makeAddAcquireOrderingTable(IRBuilder<> &IRB) {
+    constexpr int NumOrderings = (int)AtomicOrderingCABI::seq_cst + 1;
+    uint32_t OrderingTable[NumOrderings] = {};
+
+    OrderingTable[(int)AtomicOrderingCABI::relaxed] =
+        OrderingTable[(int)AtomicOrderingCABI::acquire] =
+            OrderingTable[(int)AtomicOrderingCABI::consume] =
+                (int)AtomicOrderingCABI::acquire;
+    OrderingTable[(int)AtomicOrderingCABI::release] =
+        OrderingTable[(int)AtomicOrderingCABI::acq_rel] =
+            (int)AtomicOrderingCABI::acq_rel;
+    OrderingTable[(int)AtomicOrderingCABI::seq_cst] =
+        (int)AtomicOrderingCABI::seq_cst;
+
+    return ConstantDataVector::get(IRB.getContext(),
+                                   makeArrayRef(OrderingTable, NumOrderings));
+  }
+
   // ------------------- Visitors.
   using InstVisitor<MemorySanitizerVisitor>::visit;
   void visit(Instruction &I) {
     if (!I.getMetadata("nosanitize"))
       InstVisitor<MemorySanitizerVisitor>::visit(I);
   }
 
   /// Instrument LoadInst
void visitIntrinsicInst(IntrinsicInst &I) {
 
     default:
       if (!handleUnknownIntrinsic(I))
         visitInstruction(I);
       break;
     }
   }
 
+  void visitLibAtomicLoad(CallBase &CB) {
+    IRBuilder<> IRB(&CB);
+    Value *Size = CB.getArgOperand(0);
+    Value *SrcPtr = CB.getArgOperand(1);
+    Value *DstPtr = CB.getArgOperand(2);
+    Value *Ordering = CB.getArgOperand(3);
+    // Convert the call to have at least Acquire ordering to make sure
+    // the shadow operations aren't reordered before it.
+    Value *NewOrdering =
+        IRB.CreateExtractElement(makeAddAcquireOrderingTable(IRB), Ordering);
+    CB.setArgOperand(3, NewOrdering);
+
+    IRBuilder<> NextIRB(CB.getNextNode());
+    NextIRB.SetCurrentDebugLocation(CB.getDebugLoc());
+
+    Value *SrcShadowPtr, *SrcOriginPtr;
+    std::tie(SrcShadowPtr, SrcOriginPtr) =
+        getShadowOriginPtr(SrcPtr, NextIRB, NextIRB.getInt8Ty(), Align(1),
+                           /*isStore*/ false);
+    Value *DstShadowPtr =
+        getShadowOriginPtr(DstPtr, NextIRB, NextIRB.getInt8Ty(), Align(1),
+                           /*isStore*/ true)
+            .first;
+
+    NextIRB.CreateMemCpy(DstShadowPtr, Align(1), SrcShadowPtr, Align(1), Size);
+    if (MS.TrackOrigins) {
+      Value *SrcOrigin = NextIRB.CreateAlignedLoad(MS.OriginTy, SrcOriginPtr,
+                                                   kMinOriginAlignment);
+      Value *NewOrigin = updateOrigin(SrcOrigin, NextIRB);
+      NextIRB.CreateCall(MS.MsanSetOriginFn, {DstPtr, Size, NewOrigin});
+    }
+  }
+
+  void visitLibAtomicStore(CallBase &CB) {
+    IRBuilder<> IRB(&CB);
+    Value *Size = CB.getArgOperand(0);
+    Value *DstPtr = CB.getArgOperand(2);
+    Value *Ordering = CB.getArgOperand(3);
+    // Convert the call to have at least Release ordering to make sure
+    // the shadow operations aren't reordered after it.
+    Value *NewOrdering =
+        IRB.CreateExtractElement(makeAddReleaseOrderingTable(IRB), Ordering);
+    CB.setArgOperand(3, NewOrdering);
+
+    Value *DstShadowPtr =
+        getShadowOriginPtr(DstPtr, IRB, IRB.getInt8Ty(), Align(1),
+                           /*isStore*/ true)
+            .first;
+
+    // Atomic store always paints clean shadow/origin. See file header.
+    IRB.CreateMemSet(DstShadowPtr, getCleanShadow(IRB.getInt8Ty()), Size,
+                     Align(1));
+  }
+
   void visitCallBase(CallBase &CB) {
     assert(!CB.getMetadata("nosanitize"));
     if (CB.isInlineAsm()) {
       // For inline asm (either a call to asm function, or callbr instruction),
       // do the usual thing: check argument shadow and mark all outputs as
       // clean. Note that any side effects of the inline asm that are not
       // immediately visible in its constraints are not handled.
       if (ClHandleAsmConservative && MS.CompileKernel)
         visitAsmInstruction(CB);
       else
         visitInstruction(CB);
       return;
     }
+    LibFunc LF;
+    if (TLI->getLibFunc(CB, LF)) {
+      // libatomic.a functions need to have special handling because there isn't
+      // a good way to intercept them or compile the library with
+      // instrumentation.
+      switch (LF) {
+      case LibFunc_atomic_load:
+        visitLibAtomicLoad(CB);
+        return;
+      case LibFunc_atomic_store:
+        visitLibAtomicStore(CB);
+        return;
+      default:
+        break;
+      }
+    }
+
     if (auto *Call = dyn_cast<CallInst>(&CB)) {
       assert(!isa<IntrinsicInst>(Call) && "intrinsics are handled elsewhere");
 
       // We are going to insert code that relies on the fact that the callee
       // will become a non-readonly function after it is instrumented by us. To
       // prevent this code from being optimized out, mark that function
       // non-readonly in advance.
       if (Function *Func = Call->getCalledFunction()) {

llvm/test/Instrumentation/MemorySanitizer/libatomic.ll

+; RUN: opt < %s -msan-check-access-address=0 -S -passes=msan 2>&1 | FileCheck %s
+; RUN: opt < %s -msan-check-access-address=0 -msan-track-origins=2 -S -passes=msan 2>&1 | FileCheck %s -check-prefixes=CHECK,CHECK-ORIGIN
+; RUN: opt < %s -msan -msan-check-access-address=0 -S | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @__atomic_load(i64, i8*, i8*, i32)
+declare void @__atomic_store(i64, i8*, i8*, i32)
+
+define i24 @odd_sized_load(i24* %ptr) sanitize_memory {
+; CHECK: @odd_sized_load(i24* {{.*}}[[PTR:%.+]])
+; CHECK: [[VAL_PTR:%.*]] = alloca i24, align 1
+; CHECK-ORIGIN: @__msan_set_alloca_origin
+; CHECK: [[VAL_PTR_I8:%.*]] = bitcast i24* [[VAL_PTR]] to i8*
+; CHECK: [[PTR_I8:%.*]] = bitcast i24* [[PTR]] to i8*
+; CHECK: call void @__atomic_load(i64 3, i8* [[PTR_I8]], i8* [[VAL_PTR_I8]], i32 2)
+
+; CHECK: ptrtoint i8* [[PTR_I8]]
+; CHECK: xor
+; CHECK: [[SPTR_I8:%.*]] = inttoptr
+; CHECK-ORIGIN: add
+; CHECK-ORIGIN: and
+; CHECK-ORIGIN: [[OPTR:%.*]] = inttoptr
+
+; CHECK: ptrtoint i8* [[VAL_PTR_I8]]
+; CHECK: xor
+; CHECK: [[VAL_SPTR_I8:%.*]] = inttoptr
+; CHECK-ORIGIN: add
+; CHECK-ORIGIN: and
+; CHECK-ORIGIN: [[VAL_OPTR:%.*]] = inttoptr
+
+; CHECK: call void @llvm.memcpy{{.*}}(i8* align 1 [[VAL_SPTR_I8]], i8* align 1 [[SPTR_I8]], i64 3
+
+; CHECK-ORIGIN: [[ARG_ORIGIN:%.*]] = load i32, i32* [[OPTR]]
+; CHECK-ORIGIN: [[VAL_ORIGIN:%.*]] = call i32 @__msan_chain_origin(i32 [[ARG_ORIGIN]])
+; CHECK-ORIGIN: call void @__msan_set_origin(i8* [[VAL_PTR_I8]], i64 3, i32 [[VAL_ORIGIN]])
+
+; CHECK: [[VAL:%.*]] = load i24, i24* [[VAL_PTR]]
+; CHECK: ret i24 [[VAL]]
+  %val_ptr = alloca i24, align 1
+  %val_ptr_i8 = bitcast i24* %val_ptr to i8*
+  %ptr_i8 = bitcast i24* %ptr to i8*
+  call void @__atomic_load(i64 3, i8* %ptr_i8, i8* %val_ptr_i8, i32 0)
+  %val = load i24, i24* %val_ptr
+  ret i24 %val
+}
+
+define void @odd_sized_store(i24* %ptr, i24 %val) sanitize_memory {
+; CHECK: @odd_sized_store(i24* {{.*}}[[PTR:%.+]], i24 {{.*}}[[VAL:%.+]])
+; CHECK: [[VAL_PTR:%.*]] = alloca i24, align 1
+; CHECK: store i24 [[VAL]], i24* [[VAL_PTR]]
+; CHECK: [[VAL_PTR_I8:%.*]] = bitcast i24* [[VAL_PTR]] to i8*
+; CHECK: [[PTR_I8:%.*]] = bitcast i24* [[PTR]] to i8*
+
+; CHECK: ptrtoint i8* [[PTR_I8]]
+; CHECK: xor
+; CHECK: [[SPTR_I8:%.*]] = inttoptr
+; CHECK: call void @llvm.memset{{.*}}(i8* align 1 [[SPTR_I8]], i8 0, i64 3
+; CHECK-ORIGIN: call void @__msan_set_origin(i8* [[PTR_I8]], i64 3, i32 0)
+
+; CHECK: call void @__atomic_store(i64 3, i8* [[VAL_PTR_I8]], i8* [[PTR_I8]], i32 3)
+; CHECK: ret void
+  %val_ptr = alloca i24, align 1
+  store i24 %val, i24* %val_ptr
+  %val_ptr_i8 = bitcast i24* %val_ptr to i8*
+  %ptr_i8 = bitcast i24* %ptr to i8*
+  call void @__atomic_store(i64 3, i8* %val_ptr_i8, i8* %ptr_i8, i32 0)
+  ret void
+}
+