MemorySanitizer.cpp File Reference

This file is a part of MemorySanitizer, a detector of uninitialized reads. More...

#include "llvm/Transforms/Instrumentation/MemorySanitizer.h"
#include "InstrumentationOptions.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/AttributeMask.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicsAArch64.h"
#include "llvm/IR/IntrinsicsX86.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Alignment.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TargetParser/Triple.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Instrumentation.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ModuleUtils.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <numeric>
#include <string>
#include <tuple>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "msan"

Enumerations
enum	OddOrEvenLanes { kBothLanes , kEvenLanes , kOddLanes }

Functions
	DEBUG_COUNTER (DebugInsertCheck, "msan-insert-check", "Controls which checks to insert")
	DEBUG_COUNTER (DebugInstrumentInstruction, "msan-instrument-instruction", "Controls which instruction to instrument")
static GlobalVariable *	createPrivateConstGlobalForString (Module &M, StringRef Str)
	Create a non-const global initialized with the given string.
static Constant *	getOrInsertGlobal (Module &M, StringRef Name, Type *Ty)
static VarArgHelper *	CreateVarArgHelper (Function &Func, MemorySanitizer &Msan, MemorySanitizerVisitor &Visitor)
static unsigned	TypeSizeToSizeIndex (TypeSize TS)

Variables
static const unsigned	kOriginSize = 4
static const Align	kMinOriginAlignment = Align(4)
static const Align	kShadowTLSAlignment = Align(8)
static const unsigned	kParamTLSSize = 800
static const unsigned	kRetvalTLSSize = 800
static const size_t	kNumberOfAccessSizes = 4
const char	kMsanModuleCtorName [] = "msan.module_ctor"
const char	kMsanInitName [] = "__msan_init"
static const MemoryMapParams	Linux_I386_MemoryMapParams
static const MemoryMapParams	Linux_X86_64_MemoryMapParams
static const MemoryMapParams	Linux_MIPS64_MemoryMapParams
static const MemoryMapParams	Linux_PowerPC64_MemoryMapParams
static const MemoryMapParams	Linux_S390X_MemoryMapParams
static const MemoryMapParams	Linux_AArch64_MemoryMapParams
static const MemoryMapParams	Linux_LoongArch64_MemoryMapParams
static const MemoryMapParams	Linux_Hexagon_MemoryMapParams
static const MemoryMapParams	FreeBSD_AArch64_MemoryMapParams
static const MemoryMapParams	FreeBSD_I386_MemoryMapParams
static const MemoryMapParams	FreeBSD_X86_64_MemoryMapParams
static const MemoryMapParams	NetBSD_X86_64_MemoryMapParams
static const PlatformMemoryMapParams	Linux_X86_MemoryMapParams
static const PlatformMemoryMapParams	Linux_MIPS_MemoryMapParams
static const PlatformMemoryMapParams	Linux_PowerPC_MemoryMapParams
static const PlatformMemoryMapParams	Linux_S390_MemoryMapParams
static const PlatformMemoryMapParams	Linux_ARM_MemoryMapParams
static const PlatformMemoryMapParams	Linux_LoongArch_MemoryMapParams
static const PlatformMemoryMapParams	Linux_Hexagon_MemoryMapParams_P
static const PlatformMemoryMapParams	FreeBSD_ARM_MemoryMapParams
static const PlatformMemoryMapParams	FreeBSD_X86_MemoryMapParams
static const PlatformMemoryMapParams	NetBSD_X86_MemoryMapParams

Detailed Description

This file is a part of MemorySanitizer, a detector of uninitialized reads.

The algorithm of the tool is similar to Memcheck (https://static.usenix.org/event/usenix05/tech/general/full_papers/seward/seward_html/usenix2005.html) We associate a few shadow bits with every byte of the application memory, poison the shadow of the malloc-ed or alloca-ed memory, load the shadow, bits on every memory read, propagate the shadow bits through some of the arithmetic instruction (including MOV), store the shadow bits on every memory write, report a bug on some other instructions (e.g. JMP) if the associated shadow is poisoned.

But there are differences too. The first and the major one: compiler instrumentation instead of binary instrumentation. This gives us much better register allocation, possible compiler optimizations and a fast start-up. But this brings the major issue as well: msan needs to see all program events, including system calls and reads/writes in system libraries, so we either need to compile everything with msan or use a binary translation component (e.g. DynamoRIO) to instrument pre-built libraries. Another difference from Memcheck is that we use 8 shadow bits per byte of application memory and use a direct shadow mapping. This greatly simplifies the instrumentation code and avoids races on shadow updates (Memcheck is single-threaded so races are not a concern there. Memcheck uses 2 shadow bits per byte with a slow path storage that uses 8 bits per byte).

The default value of shadow is 0, which means "clean" (not poisoned).

Every module initializer should call __msan_init to ensure that the shadow memory is ready. On error, __msan_warning is called. Since parameters and return values may be passed via registers, we have a specialized thread-local shadow for return values (__msan_retval_tls) and parameters (__msan_param_tls).

                      Origin tracking.

MemorySanitizer can track origins (allocation points) of all uninitialized values. This behavior is controlled with a flag (msan-track-origins) and is disabled by default.

Origins are 4-byte values created and interpreted by the runtime library. They are stored in a second shadow mapping, one 4-byte value for 4 bytes of application memory. Propagation of origins is basically a bunch of "select" instructions that pick the origin of a dirty argument, if an instruction has one.

Every 4 aligned, consecutive bytes of application memory have one origin value associated with them. If these bytes contain uninitialized data coming from 2 different allocations, the last store wins. Because of this, MemorySanitizer reports can show unrelated origins, but this is unlikely in practice.

Origins are meaningless for fully initialized values, so MemorySanitizer avoids storing origin to memory when a fully initialized value is stored. This way it avoids needless overwriting origin of the 4-byte region on a short (i.e. 1 byte) clean store, and it is also good for performance.

                       Atomic handling.

Ideally, every atomic store of application value should update the corresponding shadow location in an atomic way. Unfortunately, atomic store of two disjoint locations can not be done without severe slowdown.

Therefore, we implement an approximation that may err on the safe side. In this implementation, every atomically accessed location in the program may only change from (partially) uninitialized to fully initialized, but not the other way around. We load the shadow after the application load, and we store the shadow before the app store. Also, we always store clean shadow (if the application store is atomic). This way, if the store-load pair constitutes a happens-before arc, shadow store and load are correctly ordered such that the load will get either the value that was stored, or some later value (which is always clean).

This does not work very well with Compare-And-Swap (CAS) and Read-Modify-Write (RMW) operations. To follow the above logic, CAS and RMW must store the new shadow before the app operation, and load the shadow after the app operation. Computers don't work this way. Current implementation ignores the load aspect of CAS/RMW, always returning a clean value. It implements the store part as a simple atomic store by storing a clean shadow.

                 Instrumenting inline assembly.

For inline assembly code LLVM has little idea about which memory locations become initialized depending on the arguments. It can be possible to figure out which arguments are meant to point to inputs and outputs, but the actual semantics can be only visible at runtime. In the Linux kernel it's also possible that the arguments only indicate the offset for a base taken from a segment register, so it's dangerous to treat any asm() arguments as pointers. We take a conservative approach generating calls to __msan_instrument_asm_store(ptr, size) , which defer the memory unpoisoning to the runtime library. The latter can perform more complex address checks to figure out whether it's safe to touch the shadow memory. Like with atomic operations, we call __msan_instrument_asm_store() before the assembly call, so that changes to the shadow memory will be seen by other threads together with main memory initialization.

             KernelMemorySanitizer (KMSAN) implementation.

The major differences between KMSAN and MSan instrumentation are:

• KMSAN always tracks the origins and implies msan-keep-going=true;
• KMSAN allocates shadow and origin memory for each page separately, so there are no explicit accesses to shadow and origin in the instrumentation. Shadow and origin values for a particular X-byte memory location (X=1,2,4,8) are accessed through pointers obtained via the __msan_metadata_ptr_for_load_X(ptr) __msan_metadata_ptr_for_store_X(ptr) functions. The corresponding functions check that the X-byte accesses are possible and returns the pointers to shadow and origin memory. Arbitrary sized accesses are handled with: __msan_metadata_ptr_for_load_n(ptr, size) __msan_metadata_ptr_for_store_n(ptr, size); Note that the sanitizer code has to deal with how shadow/origin pairs returned by the these functions are represented in different ABIs. In the X86_64 ABI they are returned in RDX:RAX, in PowerPC64 they are returned in r3 and r4, and in the SystemZ ABI they are written to memory pointed to by a hidden parameter.
• TLS variables are stored in a single per-task struct. A call to a function __msan_get_context_state() returning a pointer to that struct is inserted into every instrumented function before the entry block;
• __msan_warning() takes a 32-bit origin parameter;
• local variables are poisoned with __msan_poison_alloca() upon function entry and unpoisoned with __msan_unpoison_alloca() before leaving the function;
• the pass doesn't declare any global variables or add global constructors to the translation unit.

Also, KMSAN currently ignores uninitialized memory passed into inline asm calls, making sure we're on the safe side wrt. possible false positives.

KernelMemorySanitizer only supports X86_64, SystemZ and PowerPC64 at the moment.

Definition in file MemorySanitizer.cpp.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "msan"

Definition at line 216 of file MemorySanitizer.cpp.

Enumeration Type Documentation

OddOrEvenLanes

enum OddOrEvenLanes

Enumerator
kBothLanes
kEvenLanes
kOddLanes

Definition at line 421 of file MemorySanitizer.cpp.

Function Documentation

createPrivateConstGlobalForString()

GlobalVariable * createPrivateConstGlobalForString ( Module & M, StringRef Str )

static

Create a non-const global initialized with the given string.

Creates a writable global for Str so that we can pass it to the run-time lib. Runtime uses first 4 bytes of the string to store the frame ID, so the string needs to be mutable.

Definition at line 656 of file MemorySanitizer.cpp.

References llvm::ConstantDataArray::getString(), llvm::Value::getType(), and llvm::GlobalValue::PrivateLinkage.

CreateVarArgHelper()

VarArgHelper * CreateVarArgHelper ( Function & Func, MemorySanitizer & Msan, MemorySanitizerVisitor & Visitor )

static

Definition at line 9559 of file MemorySanitizer.cpp.

References llvm::Triple::getArch(), llvm::Triple::hexagon, llvm::Triple::isAArch64(), llvm::Triple::isARM(), llvm::Triple::isLoongArch64(), llvm::Triple::isMIPS32(), llvm::Triple::isMIPS64(), llvm::Triple::isPPC32(), llvm::Triple::isPPC64(), llvm::Triple::isRISCV32(), llvm::Triple::isRISCV64(), llvm::Triple::isSystemZ(), llvm::Triple::x86, and llvm::Triple::x86_64.

DEBUG_COUNTER() [1/2]

DEBUG_COUNTER	(	DebugInsertCheck	,
		"msan-insert-check"	,
		"Controls which checks to insert"	)

DEBUG_COUNTER() [2/2]

DEBUG_COUNTER	(	DebugInstrumentInstruction	,
		"msan-instrument-instruction"	,
		"Controls which instruction to instrument"	)

getOrInsertGlobal()

Constant * getOrInsertGlobal ( Module & M, StringRef Name, Type * Ty )

static

Definition at line 731 of file MemorySanitizer.cpp.

References llvm::GlobalValue::ExternalLinkage, and llvm::GlobalValue::InitialExecTLSModel.

TypeSizeToSizeIndex()

unsigned TypeSizeToSizeIndex ( TypeSize TS )

static

Definition at line 1009 of file MemorySanitizer.cpp.

References llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isScalable(), kNumberOfAccessSizes, and llvm::Log2_32_Ceil().

Variable Documentation

FreeBSD_AArch64_MemoryMapParams

const MemoryMapParams FreeBSD_AArch64_MemoryMapParams

static

Initial value:

= {
    0x1800000000000, 
    0x0400000000000, 
    0x0200000000000, 
    0x0700000000000, 
}

Definition at line 340 of file MemorySanitizer.cpp.

FreeBSD_ARM_MemoryMapParams

const PlatformMemoryMapParams FreeBSD_ARM_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &FreeBSD_AArch64_MemoryMapParams,
}

Definition at line 406 of file MemorySanitizer.cpp.

FreeBSD_I386_MemoryMapParams

const MemoryMapParams FreeBSD_I386_MemoryMapParams

static

Initial value:

= {
    0x000180000000, 
    0x000040000000, 
    0x000020000000, 
    0x000700000000, 
}

Definition at line 348 of file MemorySanitizer.cpp.

FreeBSD_X86_64_MemoryMapParams

const MemoryMapParams FreeBSD_X86_64_MemoryMapParams

static

Initial value:

= {
    0xc00000000000, 
    0x200000000000, 
    0x100000000000, 
    0x380000000000, 
}

Definition at line 356 of file MemorySanitizer.cpp.

FreeBSD_X86_MemoryMapParams

const PlatformMemoryMapParams FreeBSD_X86_MemoryMapParams

static

Initial value:

= {
    &FreeBSD_I386_MemoryMapParams,
    &FreeBSD_X86_64_MemoryMapParams,
}

Definition at line 411 of file MemorySanitizer.cpp.

kMinOriginAlignment

const Align kMinOriginAlignment = Align(4)

static

Definition at line 225 of file MemorySanitizer.cpp.

kMsanInitName

const char kMsanInitName[] = "__msan_init"

Definition at line 237 of file MemorySanitizer.cpp.

kMsanModuleCtorName

const char kMsanModuleCtorName[] = "msan.module_ctor"

Definition at line 236 of file MemorySanitizer.cpp.

kNumberOfAccessSizes

const size_t kNumberOfAccessSizes = 4

static

Definition at line 234 of file MemorySanitizer.cpp.

kOriginSize

const unsigned kOriginSize = 4

static

Definition at line 224 of file MemorySanitizer.cpp.

kParamTLSSize

const unsigned kParamTLSSize = 800

static

Definition at line 230 of file MemorySanitizer.cpp.

kRetvalTLSSize

const unsigned kRetvalTLSSize = 800

static

Definition at line 231 of file MemorySanitizer.cpp.

kShadowTLSAlignment

const Align kShadowTLSAlignment = Align(8)

static

Definition at line 226 of file MemorySanitizer.cpp.

Linux_AArch64_MemoryMapParams

const MemoryMapParams Linux_AArch64_MemoryMapParams

static

Initial value:

= {
    0,               
    0x0B00000000000, 
    0,               
    0x0200000000000, 
}

Definition at line 312 of file MemorySanitizer.cpp.

Linux_ARM_MemoryMapParams

const PlatformMemoryMapParams Linux_ARM_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &Linux_AArch64_MemoryMapParams,
}

Definition at line 391 of file MemorySanitizer.cpp.

Linux_Hexagon_MemoryMapParams

const MemoryMapParams Linux_Hexagon_MemoryMapParams

static

Initial value:

= {
    0,          
    0x20000000, 
    0,          
    0x50000000, 
}

Definition at line 328 of file MemorySanitizer.cpp.

Linux_Hexagon_MemoryMapParams_P

const PlatformMemoryMapParams Linux_Hexagon_MemoryMapParams_P

static

Initial value:

= {
    &Linux_Hexagon_MemoryMapParams,
    nullptr,
}

Definition at line 401 of file MemorySanitizer.cpp.

Linux_I386_MemoryMapParams

const MemoryMapParams Linux_I386_MemoryMapParams

static

Initial value:

= {
    0x000080000000, 
    0,              
    0,              
    0x000040000000, 
}

Definition at line 260 of file MemorySanitizer.cpp.

Linux_LoongArch64_MemoryMapParams

const MemoryMapParams Linux_LoongArch64_MemoryMapParams

static

Initial value:

= {
    0,              
    0x500000000000, 
    0,              
    0x100000000000, 
}

Definition at line 320 of file MemorySanitizer.cpp.

Linux_LoongArch_MemoryMapParams

const PlatformMemoryMapParams Linux_LoongArch_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &Linux_LoongArch64_MemoryMapParams,
}

Definition at line 396 of file MemorySanitizer.cpp.

Linux_MIPS64_MemoryMapParams

const MemoryMapParams Linux_MIPS64_MemoryMapParams

static

Initial value:

= {
    0,              
    0x008000000000, 
    0,              
    0x002000000000, 
}

Definition at line 280 of file MemorySanitizer.cpp.

Linux_MIPS_MemoryMapParams

const PlatformMemoryMapParams Linux_MIPS_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &Linux_MIPS64_MemoryMapParams,
}

Definition at line 376 of file MemorySanitizer.cpp.

Linux_PowerPC64_MemoryMapParams

const MemoryMapParams Linux_PowerPC64_MemoryMapParams

static

Initial value:

= {
    0xE00000000000, 
    0x100000000000, 
    0x080000000000, 
    0x1C0000000000, 
}

Definition at line 292 of file MemorySanitizer.cpp.

Linux_PowerPC_MemoryMapParams

const PlatformMemoryMapParams Linux_PowerPC_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &Linux_PowerPC64_MemoryMapParams,
}

Definition at line 381 of file MemorySanitizer.cpp.

Linux_S390_MemoryMapParams

const PlatformMemoryMapParams Linux_S390_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &Linux_S390X_MemoryMapParams,
}

Definition at line 386 of file MemorySanitizer.cpp.

Linux_S390X_MemoryMapParams

const MemoryMapParams Linux_S390X_MemoryMapParams

static

Initial value:

= {
    0xC00000000000, 
    0,              
    0x080000000000, 
    0x1C0000000000, 
}

Definition at line 300 of file MemorySanitizer.cpp.

Linux_X86_64_MemoryMapParams

const MemoryMapParams Linux_X86_64_MemoryMapParams

static

Initial value:

= {
    0,              
    0x500000000000, 
    0,              
    0x100000000000, 
}

Definition at line 268 of file MemorySanitizer.cpp.

Linux_X86_MemoryMapParams

const PlatformMemoryMapParams Linux_X86_MemoryMapParams

static

Initial value:

= {
    &Linux_I386_MemoryMapParams,
    &Linux_X86_64_MemoryMapParams,
}

Definition at line 371 of file MemorySanitizer.cpp.

NetBSD_X86_64_MemoryMapParams

const MemoryMapParams NetBSD_X86_64_MemoryMapParams

static

Initial value:

= {
    0,              
    0x500000000000, 
    0,              
    0x100000000000, 
}

Definition at line 364 of file MemorySanitizer.cpp.

NetBSD_X86_MemoryMapParams

const PlatformMemoryMapParams NetBSD_X86_MemoryMapParams

static

Initial value:

= {
    nullptr,
    &NetBSD_X86_64_MemoryMapParams,
}

Definition at line 416 of file MemorySanitizer.cpp.