序
AddressSanitizer&ThreadSanitizer都是最初由Google开发的，用于运行时检测C/C++程序中的内存错误和多线程data race的，俗话说“Google出品，必属精品”。首先它们都非常新，最近几年才出来的，有很多先进的地方，弥补了现有一些工具的很多不足，代表了先进生产力的发展方向。比如它们都采用了CTI(CompileTime Instrumentation)技术，即在编译时进行代码插入，运行速度快，比传统的Valgrind等工具速度上要快一个数量级。它们的输出信息都非常详细，方便快速地定位问题。AddressSanitizer除了可以发现堆上内存越界外，还可以检查到栈及全局变量的越界访问，这是很多内存检查工具无法做到的。
C/C++程序员应该了解并学会使用这两个工具，相信一定可以大大提高代码质量及调查C++内存及多线程问题的效率。另外知其然知其所以然，通过此文可以来看看它们是如何实现内存越界及data race检测。由于GCC4.8之后直接提供了对这两个工具的支持，因此本文先简要介绍了如何安装GCC4.8，然后以两个简单的例子来看下它们的用法，之后大部分的篇幅都会用来介绍它们的原理及实现。
1.GCC 4.8编译安装
从GCC4.4以后GMP(GNU Multiple Precision Arithmetic Library)、MPFR就成了必须，MPC是从GCC4.6开始成为必须。由于MPFR依赖GMP，而MPC依赖GMP和MPFR，所以要先安装GMP，其次MPFR，最后才是MPC。
1.1.首先从如下地址下载GCC4.8.4版本及其依赖的gmp，mpfr和mpc
wget http://mirror.bjtu.edu.cn/gnu/gcc/gcc-4.8.4/gcc-4.8.4.tar.gz
wget http://mirror.bjtu.edu.cn/gnu/gmp/gmp-5.1.3.tar.gz
wget http://mirror.bjtu.edu.cn/gnu/mpfr/mpfr-3.1.2.tar.gz
wget http://mirror.bjtu.edu.cn/gnu/mpc/mpc-1.0.2.tar.gz
1.2.安装gmp
tar -zxvf gmp-5.1.3.tar.gz
cd gmp-5.1.3
./configure –prefix=/usr/gcc_4_8 –build=x86_64-linux-gnu
make && sudo make install
1.3.安装mpfr
tar -zxvf mpfr-3.1.2.tar.gz
cd mpfr-3.1.2
./configure –build=x86_64-linux-gnu –prefix=/usr/gcc_4_8 –with-gmp=/usr/gcc_4_8
make && sudo make install
1.4.安装mpc
tar -zxvf mpc-1.0.2.tar.gz
cd mpc-1.0.2
./configure –build=x86_64-linux-gnu –prefix=/usr/gcc_4_8 –with-gmp=/usr/gcc_4_8 –with-mpfr=/usr/gcc_4_8
make && sudo make install
1.5.安装GCC
GCC4.8
- 引入了一个新的内存错误检测工具： AddressSanitizer。使用选项-fsanitize=address能打开此检测器。 该检测器会对访存指令插装，帮助快速检测堆、栈以及全局的缓冲区溢出，以及use-after-free bug。 这个检测工具可以在Intel/PowerPC Linux系统，以及Intel Darwin上使用， ARM还不行。
- 引入了一个新的data race检测器： ThreadSanitizer。 使用选项 -fsanitize=thread能打开此检测器。头疼多线程bug调试的朋友，可以试试。
./configure –build=x86_64-linux-gnu –enable-threads=posix –prefix=/usr/gcc_4_8 –with-gmp=/usr/gcc_4_8 –with-mpfr=/usr/gcc_4_8 –with-mpc=/usr/gcc_4_8 –enable-checking=release –enable-languages=c,c++ –disable-multilib –program-suffix=-4.8
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/gcc_4_8/lib/
make && sudo make install
1.6.AddressSanitizer使用
address_test.c
int main(int argc, char **argv) {
int *array = new int[100];
delete [] array;
return array[argc]; // BOOM
}
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/gcc_4_8/lib/:/usr/gcc_4_8/lib64/
g++-4.8 -fno-omit-frame-pointer -fsanitize=address address_test.c
./a.out
=================================================================
==24558== ERROR: AddressSanitizer: heap-use-after-free on address 0x602e0001fc64 at pc 0x40082c bp 0x7fffc74fc2e0 sp 0x7fffc74fc2d8
READ of size 4 at 0x602e0001fc64 thread T0
#0 0x40082b (/home/test/GCC-4.8/test/a.out+0x40082b)
#1 0x322f61d993 (/lib64/libc-2.5.so+0x1d993)
#2 0x400678 (/home/test/GCC-4.8/test/a.out+0x400678)
0x602e0001fc64 is located 4 bytes inside of 400-byte region [0x602e0001fc60,0x602e0001fdf0)
freed by thread T0 here:
#0 0x7f8a5df4dada (/usr/gcc_4_8/lib64/libasan.so.0.0.0+0x11ada)
#1 0x4007df (/home/test/GCC-4.8/test/a.out+0x4007df)
#2 0x322f61d993 (/lib64/libc-2.5.so+0x1d993)
previously allocated by thread T0 here:
#0 0x7f8a5df4d91a (/usr/gcc_4_8/lib64/libasan.so.0.0.0+0x1191a)
#1 0x4007c8 (/home/test/GCC-4.8/test/a.out+0x4007c8)
#2 0x322f61d993 (/lib64/libc-2.5.so+0x1d993)
Shadow bytes around the buggy address:
0x0c063fffbf30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c063fffbf40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c063fffbf50: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c063fffbf60: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c063fffbf70: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c063fffbf80: fa fa fa fa fa fa fa fa fa fa fa fa[fd]fd fd fd
0x0c063fffbf90: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c063fffbfa0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c063fffbfb0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa
0x0c063fffbfc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c063fffbfd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Heap righ redzone: fb
Freed Heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack partial redzone: f4
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
1.7.ThreadSanitizer使用
thread_test.c
#include <pthread.h>
#include <stdio.h>
int Global;
void *Thread1(void *x) {
Global = 42;
return x;
}
int main() {
pthread_t t;
pthread_create(&t, NULL, Thread1, NULL);
Global = 43;
pthread_join(t, NULL);
printf("%s", "Hellow World");
return Global;
}
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/gcc_4_8/lib/:/usr/gcc_4_8/lib64/
g++-4.8 -gdwarf-2 -gstrict-dwarf -fsanitize=thread -pie -fPIC thread_test.c
./a.out
==================
WARNING: ThreadSanitizer: data race (pid=18457)
Write of size 4 at 0x7ff2a15c02e0 by thread T1:
#0 Thread1(void*) /home/test/GCC-4.8/test/thread_test.c:5 (exe+0x000000000c10)
Previous write of size 4 at 0x7ff2a15c02e0 by main thread:
#0 main /home/test/GCC-4.8/test/thread_test.c:11 (exe+0x000000000c71)
Thread T1 (tid=18458, running) created by main thread at:
#0 pthread_create ??:0 (libtsan.so.0+0x00000001eec8)
#1 main /home/test/GCC-4.8/test/thread_test.c:10 (exe+0x000000000c61)
SUMMARY: ThreadSanitizer: data race /home/test/GCC-4.8/test/thread_test.c:5 Thread1(void*)
==================
ThreadSanitizer: reported 1 warnings
2.FAQ
1.使用时有时在堆栈信息中，无法看到对应的文件及精确行号，此时很难定位问题，如何解决？
如下：
#0 0x40082b (/home/test/GCC-4.8/test/a.out+0x40082b)
#1 0x322f61d993 (/lib64/libc-2.5.so+0x1d993)
#2 0x400678 (/home/test/GCC-4.8/test/a.out+0x400678)
解决方案：
1)手动方式，参考该文章：http://www.dedoimedo.com/computers/linux-cool-hacks-4.html
可以使用addr2line直接将/home/test/GCC-4.8/test/a.out+0x400678转换为代码+行号的形式。
将如上堆栈信息存入文件t，然后执行如下命令：
cat t|awk -F"\(" ‘{print $2}’|awk -F"\)" ‘{print$1}’|awk -F"\+" ‘{print "addr2line "$2 " -f -C -e "$1}’ >tt
2)使用asan_symbolize.py自动完成
wget http://code.metager.de/source/raw/llvm/compiler-rt/lib/asan/scripts/asan_symbolize.py
该文件依赖于argparse模块，该模块是在python2.7之后引入的，如果机器上的python版本低于2.7，还需要先安装argparse模块才能正常使用。
./a.out 2>&1|python asan_symbolize.py|c++filt
3)与GDB结合使用，具体方式见下面
2.低版本GCC(4.1.2)编译没问题，换成高版本GCC(4.8.4)编译报错
由于AddressSanitizer&ThreadSanitizer是在GCC4.8才开始引入的，因此要想使用它们，必须要采用新版GCC。但是很多现有代码都是用较低版本的GCC编译的，把编译器升级到GCC4.8，编译现有代码时通常都会碰到一些编译错误，比如出现如下错误：
error: ‘int64_t’ does not name a type
error: ‘int64_t’ has not been declared
原因：
http://stackoverflow.com/questions/11069108/uint32-t-does-not-name-a-type
解决方式：
需要在报错的文件中显示引入一些必需的头文件。
3.检测到问题时打印的各种信息的含义？
AddressSanitizer的输出如下：
==24558== ERROR: AddressSanitizer: heap-use-after-free on address 0x602e0001fc64 at pc 0x40082c bp 0x7fffc74fc2e0 sp 0x7fffc74fc2d8
READ of size 4 at 0x602e0001fc64 thread T0
#0 0x40082b (/home/test/GCC-4.8/test/a.out+0x40082b)
#1 0x322f61d993 (/lib64/libc-2.5.so+0x1d993)
#2 0x400678 (/home/test/GCC-4.8/test/a.out+0x400678)
Shadow bytes around the buggy address:
Shadow byte legend (one shadow byte represents 8 application bytes):
最重要的信息有两个一个是发生越界的代码行，一个发生越界的内存地址及其所对应的程序变量，根据这两个内容然后再结合代码一般都可以定位。另外输出中除了发生错误那一刻对应的堆栈信息外，还有该内存被malloc时的堆栈，以及shadow bytes信息，关于shadow bytes的含义在看过原理那一节理解原理后应该就明白了。
ThreadSanitizer的输出可以参考如下文章：
How to understand the reports produced by ThreadSanitizer
4.有时候直接运行看结果可能还不够，如何与GDB结合使用?
可以通过在GDB中设置如下断点，然后执行gdb即可
break __asan_report_error
5.运行时如果加上AddressSanitizer出现segfault错误，如果不加则没问题，何故？
此处主要解释下我们通常通过dmesg看到的那条segfault信息segfault at 10 ip 00007f9bebcca90d sp 00007fffb62705f0 error 4 in libQtWebKit.so.4.5.2[7f9beb83a000+f6f000]
at后面的地址是发生段错误时要访问的内存地址
ip，instruction pointer，当前正在执行的指令地址
sp，stack pointer
error，page fault error code，每个bit代表了一个含义，比如error=4，表示第“The cause was a user-mode read resulting in no page being found”，各bit的具体定义如下：
/* * Page fault error code bits * bit 0 == 0 means no page found, 1 means protection fault * bit 1 == 0 means read, 1 means write * bit 2 == 0 means kernel, 1 means user-mode * bit 3 == 1 means use of reserved bit detected * bit 4 == 1 means fault was an instruction fetch */ #define PF_PROT (1<<0) #define PF_WRITE (1<<1) #define PF_USER (1<<2) #define PF_RSVD (1<<3) #define PF_INSTR (1<<4)de>
libQtWebKit.so.4.5.2[7f9beb83a000+f6f000]，表示segfault发生的对象是libQtWebKit.so.4.5.2，7f9beb83a000表示运行时该so加载的基地址，f6f000表示该对象所占空间的大小。ip的值应该在[7f9beb83a000,7f9beb83a000+f6f000]区间内。对于二进制程序来说直接通过ip应该就可以找到对应代码。但是对于so来说，还要通过ip-so基地址=0x7f9bebcca90d-0x7f9beb83a000=0x49090D，可以计算出segfault发生时的指令在so内的offset。然后结合addr2line则可以看到对应的指令及代码：
addr2line -e ./usr/lib64/qt45/lib/libQtWebKit.so.4.5.2 -fCi 0x49090D
Event for a shared lib, the "[3c0ac00000+20000]" part should give a hint where the crashing segment of the lib was mapped in memory. "readelf –segments mylib.so" lists these segments, and then you can calculate the EIP offset into the crashing segment and feed that to addr2line (or view it in "objdump -dgS").
3.AddressSanitizer原理
3.1.内存错误检测常用机制
Shadow Memory，为了实现检测，很多工具都会为应用数据额外分配一块对应的shadow memory来存储相关的元数据。常见方法有两种：一种是直接将实际地址进行缩放+偏移映射到一个shadow地址，从而将整个的应用程序地址空间映射到一个shadow地址空间；一种是增加额外的地址转换表，通过查表完成实际地址到shadow地址的转换。比如Valgrind和Dr.Memory就是将shadow地址分成多个片段，然后通过查找表转换shadow地址。而AddressSanitizer则采用了直接缩放+偏移的方式。
Instrumentation(代码插桩)，很多内存错误检查工具都是采用的binary Instrumentation，所谓binary Instrumentation也就是说是对编译出的binary在运行时进行代码插桩，比如我们所熟知的Valgrind,Dr.Memory,Purify,Intel Parallel Inspector都是采用的这种技术，这些工具可以无误报的发现堆内存越界及use-after-free错误，但是据我们所知基于binary Instrumentation的工具无法发现栈及global对象的越界访问。需要补充的一点是，他们可以发现UMR(Uninitialized Memory Read)，对于这这种错误AddressSanitizer不会进行检查，但是后面要介绍的MemorySanitizer则是专门用来检查这种错误的。此外，虽然目前GCC上的AddressSanitizer还不支持，但是原版的AddressSanitizer还可以进行如下检查：内存泄露，全局变量初始化顺序，Use-After-Return。
与binary Instrumentation相对的是source Instrumentation，也称作compile-time instrumentation。Mudflap就是采用的编译时代码插入技术，因此它可以检测到栈对象的越界访问。但是，由于它并没有在栈帧上的每个对象之间插入redzone，因此无法发现所有的栈缓冲区溢出bug，同时对于复杂C++代码还存在误报的问题。AddressSanitizer采用了compile-time instrumentation，并且在栈帧上的每个对象之间插入redzone，因此可以发现栈及global对象的相关越界访问。
Debug Allocators，还有一类内存错误检测器是通过特制的内存分配器来实现的，同时不会改变剩余部分的执行过程。像Electric Fence [25], Duma [3], GuardMalloc[16] and Page Heap [18]这些工具，它们利用了CPU的页保护机制。每个已分配空间由一个page(或一组page)组成，然后在它的左边和/或右边分配一个额外的page，并且将这个额外的page标记为不可访问的。对它的访问将产生一个page fault，然后将其报告为一个越界访问错误。采用这种机制，引入了非常大的额外内存，同时对于malloc操作比较频繁的应用性能有很大降低，因为每个malloc操作将至少需要一次系统调用。同时这种工具还无法检查出某些种类的bug。其他的一些malloc实现，像DieHarder,Dmalloc，它们会修改malloc函数，为malloc的区域周围添加redzone并将其置上magic value，在free的时候也会为已释放的内存区域置上magic value。当读到一个magic value时就认为程序访问了越界或未初始化的value。也可以通过选择不同的magic value，然后运行几次，观察这几次运行结果是否相同，不过这种方式都是拼的概率，并不能保证100%检查出来。同时这种方式，无法在错误发生时就立刻检查出来，比如redzone被错误的覆盖了，只能在后面被检查出来，这样就相当于只是告诉你"程序有bug"，但是难以帮助定位问题。同时debug malloc工具，也无法处理栈和全局对象的情况。
类似的magic value的方式也常被用于栈的溢出检查中。比如StackGuard [29] and ProPolice[14]会在local变量和当前栈帧的返回地址之间放置一个Canary Value，然后在函数退出时检查该value值的一致性。这种方法可以防止栈因缓冲区溢出被破坏，但是没法检查出针对栈内对象的任意的越界访问。
3.2.AddressSanitizer原理
AddressSanitizer: A Fast Address Sanity Checker
AddressSanitizer可以发现堆/栈/全局对象的越界访问，以及use-after-free类型的bug。它通过采用特殊的内存分配器及代码插桩技术来进行检测。目前业界已有几十个内存错误检查工具，它们的差别主要体现在速度，内存开销，能检测到的bug类型，检查出bug的概率，支持的平台上。对于AddressSanitizer来说，兼具了高效及高覆盖率，性能平均只有73%的下降，内存开销是原来的3,4倍。
AddressSanitizer主要由两部分组成：代码插桩模块和运行时库。代码插桩模块会对code进行修改以在每次内存访问时检查shadow state，同时负责在栈和全局对象周围创建用于检测overflow和underflow的poisoned redzones。运行时库，会替换掉malloc/free，完成如下相关功能：在堆空间周围创建用于检测的poisoned redzones，延迟已被free的堆空间的重用(正常情况下为提高内存使用率，已经被free的内存是可以被重用的，但是对于AddressSanitizer来说，因为要检查use-after-free错误，因此被free的空间会被放到一个队列中，这些来确保已被free的内存如果还会被使用的话能够被发现，当然该队列还是有一定的大小限制，按照FIFO的原则进行退出)，同时还会负责报告错误。
从整体上看，AddressSanitizer采用的方法类似于基于Valgrind的工具AddrCheck：采用Shadow Memory来记录应用程序的每一字节是否可以安全地访问，同时采用代码插桩技术来针对应用的每次load和store对Shadow Memory进行检查。但是AddressSanitizer采用了一种更高效的Shadow映射方式，一种更紧致的Shadow编码技术，除了可以对堆进行检查外还可以检查栈和global对象，另外它要比AddrCheck快一个数量级。
Shadow Memory，由于malloc函数返回的地址通常都至少是8字节对齐的。这样我们可以得出如下观察，对于应用程序堆内存上任意已对齐的8字节序列来说，它只有9种状态：前k(0=<k<=8)个字节是可寻址的，剩余8-k个不是。这样这个状态就可以通过一字节的Shadow Memory进行表示。
AddressSanitizer会将虚拟地址空间的1/8作为Shadow Memory，通过对实际地址进行缩放+offset直接将它们转换到对应的Shaodw地址。假设应用程序内存地址为Addr，那么其对应的Shadow地址为(Addr>>3)+Offset。如果虚拟地址空间的最大合法地址为Max-1，那么Offset值的选择需要确保从Offset到Offset+Max/8在启动时不会被占用。对于常见的32位Linux和MacOS系统来说，其虚拟地址空间为0x00000000-0xffffffff，我们令Offset = 0x20000000 (2^29)。对于具有47个地址位的64位系统来说，我们令Offset =0x0000100000000000 (2^44)。
图1展示了地址空间的分布。应用程序内存被分为low和high两部分，它们被映射到对应的Shadow区域，而Shadow区域的地址则被映射到bad区域，它们会通过页保护机制设置为不可访问的。
每个Shadow Byte采用如下编码：0表示对应应用程序内存区域的所有8个字节都是可访问的，k表示前k个字节是可以访问的，负值表示所有8个字节都是不可访问的。同时我们采用不同的负值来标示不同类型的不可访问地址。如上文中的：
Heap left redzone: fa
Heap righ redzone: fb
Freed Heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack partial redzone: f4
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
这种Shadow Mapping机制可以扩展为如下形式：(Addr>>Scale)+Offset，Scale可以取的值为1……7{!超过7的话，将无法用一个字节来描述应用程序中2^N字节对应的状态了，因为一个字节虽然可以描述2^8个状态，但是最高位为1的用来描述各种非法状态了，因此剩下的最多可以描述2^7个字节的连续内存的有效状态(前1,2,3,4…2^7字节可访问)，同时这也是论文原文中第1节中为何说可以达到"128-to-1 mapping"的原因，即N=7的情况：2^7=128}。设Scale为N，那么Shadow内存将会占用虚拟内存空间的1/2^N，redzone的最小大小(malloc的对齐)为2^N字节，每个Shadow Byte可以描述2^N字节的状态，编码成2^N+1个不同的值。
Scale值越大，所需的Shadow内存越少，但是需要更大的redzone大小来满足对齐的需求。在Scale值大于3时，需要为8字节访问进行更复杂的代码插入。但是这为那些没办法放弃1/8的地址空间的应用程序提供了灵活性。
代码插桩。对于8字节的内存访问来说，AddressSanitizer会计算出对应的Shadow Byte地址，然后load该byte数据，检查其值是否为0，如下：
ShadowAddr = (Addr >> 3) + Offset;
if (*ShadowAddr != 0)
ReportAndCrash(Addr);
对于1-,2-或4-字节访问，插入的代码也稍微更复杂些：如果shadow value为正(比如，8字节中只有前k个字节是可访问的)，我们还需要将该地址的末3位与k进行比较，确保没有越界。如下：
ShadowAddr = (Addr >> 3) + Offset;
k = *ShadowAddr;
if (k != 0 && ((Addr & 7) + AccessSize > k))
ReportAndCrash(Addr);
这两种情况都是为原始代码中的每一次内存访问(读&写)增加了一次内存读。
我们将AddressSanitizer的代码插桩过程放到LLVM优化流水线中非常靠后的位置，这样我们就只会对那些经过LLVM优化器优化后残余的内存访问进行插桩，减少了不必要的插入。比如那些被LLVM优化掉的栈访问将不会被插桩。
错误报告代码(ReportAndCrash(Addr))最多只会被执行一次{!AddressSanitizer的机制是一旦检测到一个错误，就直接报告错误退出，这样做的理由是实现简单，也减少了记录所有错误的开销}，但是会被插入到代码的很多地方，因此需要确保它的紧凑性。目前我们是把它作为一个简单的函数调用。另一种可能的选择是调用一个可以产生硬件异常的指令。
运行时库。运行时库的主要目的就是管理Shadow Memory。在应用程序启动时，整个Shadow空间将会被map，以保证程序其他部分无法使用它。Shadow Memory的Bad段将会被置为保护态。在Linux系统上，Shadow区域总是会在启动时就占住。在MacOS上，需要手动关闭ASLR。malloc和free将会被特制的实现替换掉，malloc会在返回的内存区域周围，设置redzone，redzone将会被标记为不可访问的或者说是有毒的(poisoned)。redzone区域越大，可以检查出越大的向上或向下溢出。在分配器内部，会维护一个每个规模大小的对象及其对应freelist的数组。对于n个内存区域，会分配对应的n+1个redzone，这样某个区域的右边的那个redzone通常是另一个区域的左边的redzone。
左边的redzone会被用来存储分配器的内部数据(比如分配的内存大小，线程ID等)。因此当前heap redzone最小大小为32字节。free函数会对整个内存区域染毒，同时将它放到隔离区(quarantine)，这样该区域就不会很快再被malloc分配出去。当前隔离区是采用一个任意时刻持有固定大小内存的FIFO队列实现的。
默认情况下，malloc和free会记录当前的调用栈以为bug报告提供更多信息{!也就是说这个是可以关掉的，可以通过运行时flag进行设置，但是打开它可以快速定位到内存是什么时候怎么样被malloc或free的，这个很有用，很多工具通常只能看到出错那一刻的调用栈}。malloc的调用栈是存放在左边的redzone，因此redzone越大可以存放愈深的调用栈信息。而free的调用栈则是存放在内存区域自己的开始位置。{!malloc的调用栈信息是在发生越界访问时，用来报告该内存被malloc时的上下文信息，此时该内存区域还在使用，所以栈信息不能放到内存区域，但是可以放到redzone区域。Free的调用栈则是在发生use-after-free时提供free调用信息的，free之后内存区域已经不会被使用，所以可以用来存放free的调用栈信息。另外在发生use-after-free错误时，为了能够同时显示malloc和free的调用栈，因此free也不能重用malloc所用的redzone空间}
栈及全局对象。为了能够检查出全局及栈对象的越界访问，AddressSanitizer必须要在这些对象周围创建redzone。对于全局对象来说，redzone是在编译时创建的，同时在应用程序启动时这些地址会被传给运行时库。运行时库会负责这些redzone进行染毒，并记录这些地址用于将来的错误报告。
对于栈对象来说，redzone是在运行时进行创建和染毒的{!这里的运行时创建和染毒，应该这么理解，栈对象的分配是运行时完成的，因此redzone的创建是运行时进行的，染毒操作是由插入代码完成的，但是该代码也是在运行时才会被执行，因此染毒也是运行时完成的}。当前采用了32字节大小的redzone，比如给定如下程序：
void foo() {
char a[10];
<function body> }
转换后的代码如下：
void foo() {
char rz1[32]
char arr[10];
char rz2[32-10+32];
unsigned *shadow =
(unsigned*)(((long)rz1>>8)+Offset);
// poison the redzones around arr.
shadow[0] = 0xffffffff; // rz1
shadow[1] = 0xffff0200; // arr and rz2
shadow[2] = 0xffffffff; // rz2
<function body>
// un-poison all.
shadow[0] = shadow[1] = shadow[2] = 0; }
为何要在函数退出时进行un-poison呢？可以与下面的那个Clone调用报错结合来看，如果不去un-poison在Clone调用存在的时候会导致报错。另外对于栈来说，此次函数调用中的shadow变量对应的内存地址空间，在后面运行中可能被作为其他函数内部变量的地址空间。
漏报&误报。
受当前机制的影响，AddressSanitizer在某些情况下会发生漏报。
1)那些产生局部越界的未对齐的内存访问。如下
int *a = new int[2]; // 8-aligned
int *u = (int*)((char*)a + 6);
*u = 1; // Access to range [6-9]
根据前述的shadow计算方法，u这个地址会被左移3位，实际上得到的ShadowAddr与a没啥区别，这样k = *ShadowAddr;直接就是0，而不会报错。目前AddressSanitizer没有解决这个问题，因为目前能够想到的解决方案都会造成性能损失。
2)跳过redzone的越界访问，如下：
char *a = new char[100]; char *b = new char[1000]; a[500] = 0; // may end up somewhere in b
陷入到redzone的越界访问，100%会被检测到，但是如上的越界访问，可能刚好已经落到b分配的合法空间内了。如果内存充足，推荐采用128字节的redzone。
3)如果在free和下次use之间，又发生了大量内存的分配和释放，use-after-free错误可能无法被检测到，如下：
char *a = new char[1 << 20]; // 1MB
delete [] a; // <<< "free"
char *b = new char[1 << 28]; // 256MB
delete [] b; // drains the quarantine queue.
char *c = new char[1 << 20]; // 1MB
a[0] = 0; // "use". May land in ’c’.
简单来说，AddressSanitizer不存在误报的情况。但是在AddressSanitizer的开发和部署过程中，也碰到了一些非期望的bug报告。
1)与编译器的Load Widening发生冲突，如下代码：
struct X { char a, b, c; };
void foo() {
X x; …
… = x.a + x.c; }
在该代码中，对象x是3字节大小，4字节对齐的。Load Widening会将x.a+x.c转换成一个4字节的load。按照之前的栈代码插入方式，第4个字节应该是被染毒的，这样在load这4个字节时，就会报错。通过在LLVM中临时关闭load widening解决。
2)与Clone冲突。我们还曾经碰到几次误报都是伴随着clone系统调用出现的。首先进程，采用CLONE VM|CLONE FILES调用了clone，该操作会创建一个与父进程共享内存的子进程。特别是，子进程的栈使用的内存也是属于父进程的。然后子进程调用了一个包含栈上对象的函数，此时AddressSanitizer会将栈对象的redzone区域染毒。最后，子进程调用了一个不会return的函数(比如_exit或exec)，这样该函数对redzone进行消毒(un-poisoning)的那部分代码就不会被执行。这样父进程地址空间仍处于染毒状态，当该内存被再次使用时就会报错。我们通过找到所有的never-return函数(像_exit或exec这样具有该属性的那些函数)，然后在调用它们之前将整个栈内存消毒。与之类似，AddressSanitizer还必须要对longjmp和C++异常进行拦截。
有时候，我们可能想不对某些部分进行内存检查，比如某些底层代码可能会直接对栈上的两个地址之间的内容进行跨多个栈帧的迭代访问，不能对它们进行代码插桩。AddressSanitizer提供了no_sanitize_address 属性，具体参见Turning off instrumentation。
AddressSanitizer是线程安全的，因为它只会在应用程序内存数据不可访问时(在malloc和free内部，在栈帧被创建和销毁时，在模块初始化时)才会对它进行修改。所有其他针对Shadow Memory的访问都是只读的。malloc和free实现采用了thread-local cache来避免锁的使用。如果原始程序在内存访问与delete间存在竞争，那么AddressSanitizer可能会将它检测为use-after-free错误，但是不保证一定可以检测到。每个malloc和free调用都会记录对应的线程ID，同时在对应的错误报告中会提供线程创建的调用栈。
3.3.精度与资源使用tunning
如下三个因素会影响AddressSanitizer的精度及资源使用，这三个值都是由环境变量控制，可以在程序启动时设置：
1)Depth of stack unwinding (default: 30)。对于每个malloc和free调用，该工具都会对调用栈进行unwind以为错误报告提供更多信息。该选项会影响工具的执行速度，尤其是对于那些属于malloc调用密集型的调用来说。它不会影响内存占用及查找bug的能力，但是调用栈太短的话不利于定位问题。
2)Quarantine size (default: 256MB)。即保存到前面提到的FIFO队列中的已free的内存空间大小之和，这个值会影响发现use-after-free类型bug的能力。但是它不影响性能。
3)Size of the heap redzone (default: 128 bytes)。该选项会影响发现堆异常类型bug的能力。该值越大，会导致性能变低并且占用更多内存，尤其是对那些进行了很多小块内存分配的程序来说。由于redzone会被用来保存malloc的调用栈，因此减少这个值，会导致最大unwinding深度变小。
4.ThreadSanitizer原理
4.1.Data Race
What Every Programmer Should Know About Races
Description of some most popular data races
Definitions and types of High-Level Data Races
Description of atomic reference counting and challenges for race detectors
数据竞争，是指这样一种情况：两个线程并发访问同一共享内存地址，并且其中至少有一个是写操作。这种bug通常很难定位及复现。但是这种竞争通常可能导致数据破坏或段错误，而将数据竞争完全精确的检测出来已知是一个NP-hard问题。但是创建一种具有可接受精度的数据竞争检测工具却是可能的(可能伴随着漏报或误报)。
三种基本的数据竞争检测技术是：static，on-the-fly和postmortem。后两者也通常被称为动态竞争检测技术。静态竞争检测器，是指直接对程序的源代码进行分析。而动态竞争检测器则会对特定的程序执行轨迹进行分析，on-the-fly，则是在程序运行的同时进行事件的分析，而postmortem则会把这样的事件存到临时文件中，在程序运行完成之后对文件内容进行分析。
绝大多数的动态数据竞争检测工具都是基于如下几种算法：happens-before, lockset或混合模式(两者兼而有之)。这些算法都可以运用到on-the-fly和postmortem分析中。
4.2.ThreadSanitizer概述
ThreadSanitizer – data race detection in practice
Data race detection algorithm used by ThreadSanitizer
在2007年底的时候，我们尝试了几种现有的竞争检测器，即便是其中的佼佼者如Helgrind，也存在很多误报和漏报。Helgrind采用了一种混合算法，2008年比较早的时候我们修改了Helgrind的混合算法。并且增加了一种纯Happens-before模式，虽然这种模式几乎没有什么误报，但是与之前的混合算法相比漏报却更严重了。同时，Helgrind的运行效率也无法达到我们的期望，它还是运行地太慢，同时在纯Happens-before模式下会漏掉很多竞争情况，在混合模式下有存在太多的噪音。因此到了2008年底，我们就实现一个自己的竞争检测器，我们称之为“ThreadSanitizer”。它采用了一种新的混合算法，可以方便地运行在纯Happens-before模式下，它也支持动态的annotations。同时我们让竞争报告尽可能地易读。
ThreadSanitizer采用的是动态检测技术，它不会扫描分析源代码，而是以程序运行中产生的一系列离散的事件点为输入，进行分析，从而找到竞争。最重要的事件就是内存访问和同步。内存访问即Read和Write，同步事件则要么是锁事件要么是Happens-before事件。锁事件又分为WrLock，RdLock，WrUnLock，RdUnLock。Happens-before事件则分为Signal和Wait。这些事件由运行程序产生，经由底层binary translation框架(Valgrind)的帮助交给ThreadSanitizer。
在进行进一步的介绍之前，我们需要先来认识两个竞争检测算法：LockSet-Based与Happens-before。以下内容来自：Hybrid Dynamic Data Race Detection这篇文章。
4.3.LockSet-Based竞争检测
基于这样一个假设：无论何时只要两个不同的线程访问了相同的共享内存地址，并且其中一个为写操作，那么这两次访问操作必须要持有某一个共同的锁。当该假设被违反时，我们就视为具有潜在的竞争情况。可以用如下公式来描述：
即两个线程ti,tj前后两次针对同一个内存地址(mi,mj,mi=mj)的访问，至少存在一个写操作，并且没有持有共同的锁。MEM(m,a,t)，m代表内存地址，a代表访问类型，t代表线程。Li(t)表示的是线程t在第i步时持有的锁集合，可以通过锁事件(lock&unlock)来进行计算。Li(ti)与Lj(tj)的交集为空，即表明线程ti和tj在访问相同的内存区域时没有加锁保护。为了方便理解整个检测过程，可以将整个程序执行过程看做是串行的，检测过程看做是事后进行的，这样针对每个内存访问事件，计算出当时对应线程持有的锁集合，然后对于那些访问相同内存区域的事件，两两比较，看是否满足上述竞争条件即可完成检测。但是违反了lockset假设，并不一定代表了真的是程序错误。因为实际上程序员不是必须要通过对共享数据进行锁保护才能写出多线程安全的代码的，因此这种方式容易出现误报，但是它开销比较低。比如如下程序就会被误报，lockset交集为空，但是实际上它是没有问题的，因为通过queue保证了两个线程不会同时访问该对象。
Happens-before概念最初是由Lamport提出用于描述分布式系统的{!论文Time Clocks and the Ordering of Events in a Distributed System}，在这里我们将它用来描述进程内部多个线程之间的关系。Happens-before关系可以定义如下：
1. 两个事件ei,ej如果同属于一个线程，并且ei发生在ej之前，那么我们就说i->j (i happen before j)
2. 如果ei是消息g的发送方，ej是消息g的接收方，那么我们也说i->j
Happens-before具有传递性，即：i->j & j->k可以推出i->k
上面的消息，具体到java线程来说，就是各种同步操作：start()，join()，wait()，notify()和notifyall()。比如线程t1启动了线程t2，就意味着产生了一个消息g，同时对应了两个事件SND(g,t1)和RCV(g,t2)。其他类似。
但是要进行full happens-before检测，我们还需要增加一些新的线程消息来捕获线程间因locking而产生的交互。对于同一个锁对象来说，如果线程t1是unlock，t2是lock，我们也认为t1 happens-before t2，就产生一个SND(g,t1)，然后在下面线程t2拿到锁时再产生一个RCV(g,t2)。将这些关系建立起来之后，下面就看怎么根据这些关系，检测竞争。实际上，happens-before竞争检测也是非常简单的：如果我们观察到两个事件ei和ej，它们访问了相同的内存位置，同时至少一个是Write操作，同时既没有i->j，也没有j->i，我们就认为存在潜在的竞争。
也就是说如果两个线程访问了同一个内存地址，但是这两次访问之间又没有Lamport定义的那种happens-before关系，我们就认为它们之间存在潜在的竞争。这种方式与LockSet-Based相比，具有更少的误判，实际上只要是它报告的竞争都是说明实现上存在可以改进的线程调度问题，但是另一方面它存在更多的漏报。当然作为动态检测技术，这两种方法都存在漏报，因为它们的检测依赖于实际的程序执行过程。full happens-before检测需要将unlock与lock也作为happens-before关系，但是如果不建立锁的happens-before关系的话就存在误报，基本就没法用了。比如如下存在竞争的程序就会被漏报：
简单来说：锁和Happens-before都是保证了两个线程不会同时访问同一内存地址。锁通过互斥保证，Happens-before则建立了不同线程中事件先后的偏序关系。没有这些就意味着存在潜在竞争。Lockset based要求更严，因此存在误报，但是不会漏报。Happens-before要求更松，因此存在漏报，但是不会误报(除非采用了lock-free算法等特殊情况)。两者优势互补，因此后面就有了基于二者的混合模式：锁用Lockset-Based，不再为Unlock/lock建立happen before关系，剩下的再用happens-before。但是这种模式仍然存在误报(比如上面的那个误报依然无法解决)。
另外在理解竞争检测算法时，还是要从各个线程发生的事件来考虑，而不是从线程的实现代码上来考虑。也就是说在每一次检测中，每个线程都对应了一系列前后发生的事件，然后去判断这些事件间的happens-before关系(或lockset存在交集)，在那些没有此类关系的事件中，如果访问了相同的内存区域，那么就说明存在竞争。
Tid(线程ID)：程序中线程的唯一标识符
ID：某一内存位置对应的标示符
EventType：Read, Write, WrLock, RdLock,WrUnlock, RdUnlock, Signal, Wait
Event：由{EventType,Tid,ID}组成的三元组，写作EventTypeTid(ID)或者Tid显而易见时也写作EventType(ID)
Lock：出现在某一个Locking事件中的ID
在某一时间点，如果观察到的WrLockT(L)事件次数大于WrUnLockT(L)事件次数，我们就说锁L被线程T write-held。如果锁L被线程T write-held或者是观察到的RdLockT(L)事件次数大于RdUnLockT(L)事件次数，我们就说锁L被线程T read-held。
Lock Set(LS)：一组锁集合。
Writer Lock Set(LSwr)：给定线程所持有的所有write-held锁组成的集合。
Reader Lock Set(LSrd)：给定线程所持有的所有read-held锁组成的集合。
Event Lock Set：对应一个Write事件的LSwr和对应一个Read事件的LSrd。
Event Context：用于帮助用户了解事件发生环境的信息。通常都是一个堆栈信息。
Segment：某个线程只包含内存访问事件(比如没有同步事件)的一个事件序列集合。Segment的上下文用处于该Segment的第一个事件的上下文来表示。每个Segment都有它所对应的LSwr和LSrd。每个内存访问只从属于一个Segment。
Happens-before arc：满足如下关系的一个事件对，X=SignalTx(Ax),Y= WaitTy(Ay),Ax=Ay && Tx!=Ty && X先被观察到。
Happens-before：事件之间存在的一种偏序关系。X=TypeXTx(Ax),Y= TypeYTy(Ay)满足如下条件之一：
1.Tx=Ty
2.{X,Y}具有Happens-before arc
3.存在E1,E2，X<=E1<E2<=Y
Happens-before关系可以自然的推广到Segment之间，因为Segment内部并不包含同步事件。
Segment Set：由一系列Segment {S1…Sn}组成的集合，并且任意两个Segment之间不存在Happens-before关系。
Concurrent：如果两个内存访问事件X，Y满足如下条件：它们不存在Happens-before关系并且它们的lock Set集合不存在交集，我们就认为它们是Concurrent的。
Data Race：另个线程Concurrently地访问了同一个共享内存位置，同时至少一个操作为Write类型。
ThreadSanitizer的状态由global的和per-id的状态组成。Global状态是指那些目前为止所观察到的同步事件(lock-sets,happens-before arc)信息。Per-ID状态(又称shadow memory或metadata)，保存了当前运行程序的所有内存位置。
ThreadSanitizer的Per-ID状态包含两种Segment集合：writer Segment集合SSwr和reader Segment集合SSrd。一个给定ID所对应的SSwr是指针对该ID的write操作所在的Segment组成的集合。SSrd则是指针对该ID的read操作所在的满足如下条件的所有Segment组成的集合：所有属于SSrd的Segment都非happens before SSwr中的任意Segment，即都是happen after或者没有相关关系。
每个内存访问都会经过如下函数的处理。它会对SSwr和SSrd进行增删，以确保它们满足上述定义。最后，它会检查当前状态是否存在竞争。具体实现如下：
考虑上面程序的整个运行过程，Seg肯定是后来发生的，因此肯定满足Seg非happen before s，同时又要保证s非happensbefore Seg。这样最终SSwr里的各Seg相互之间肯定都是没有happens-before关系的。{?但是对此还有个疑问，比如在更新SSwr和SSrd时，会把那些happen before Seg的s去除，但是有没有可能是被去掉的s与后面的某些新的Seg’有竞争，而Seg与Seg’没有，这样是否可能造成漏报呢？比如S1,S2,S3，它们分属不同线程但都访问了同一个内存位置，S1与S2存在happen before关系，S2和S3有锁保护，那么按照上面的算法是不是就不会发现S1和S3之间的竞争呢？当然可能也可以理解为与实际运行顺序相关，即动态检测本身的缺陷所导致的。比如换个顺序S3,S1,S2的话是能发现这个竞争的。另外，程序实际执行中以S3,S1,S2的顺序执行，可能也不会有问题，但是竞争检测却能检测到竞争，这也是竞争检测工具的意义}
是否存在竞争判断方法如下：
ThreadSanitizer有三种不同的模式可供用户选择，以调整Segment的大小及上下文信息的精细程度。默认为1：每当程序进入一个超级块就创建一个Segment，因此事件发生的上下文可以锁定到一个小的代码区域，通常都是在一个函数内部，虽然堆栈顶层对应的代码行数是不准，但是其他层堆栈的信息则是准的。0(fast模式)：只有在发生同步事件后才创建Segment，该模式通常只用于进行回归测试。2(precise,slow模式)：每个内存访问创建一个Segment，可以给出精确的堆栈信息，但是运行非常慢，实际中也比较少用。
对happens-before关系稍作扩展，我们就可以把上面的状态机由hybrid模式变成pure-happens-before模式。即将locking事件也用happens-before进行刻画，如下：
X = WrUnlockT1 (L), Y = WrLockT2 (L)
X = WrUnlockT1 (L), Y = RdLockT2 (L)
X = RdUnlockT1 (L), Y = WrLockT2 (L)
(X, Y ) is a happens-before arc.
http://lwn.net/Articles/598486/
http://sdtimes.com/google-redesigns-threadsanitizer-for-c-and-go/
http://blog.chromium.org/2014/04/testing-chromium-threadsanitizer-v2.html
Finding races and memory errors with compiler instrumentation
上面一节关于ThreadSanitizer算法内容的介绍来自于发表于2009年的论文“ThreadSanitizer – data race detection in practice”，当时的实现采用的技术还是基于Valgrind的binary translation。Tsan V2版本采用了与基于Valgrind的原始版TSan相同的竞争检测算法，但是不再基于Valgrind而是直接采用了编译时插桩技术，速度因此得到了很大提升，与原始程序相比只有2-4倍的速度下降。根据该slide，v1与v2对比如下：
目前GCC4.8用的已经是Tsan V2版本。除了数据竞争之外，它还可以检测出其他类型的bug，包括死锁、use-after-free竞争等，它也能识别出原子性操作。根据相关报告，它比最初的Tsan实现快了20多倍。
void foo(int *p) {
*p = 42;
}
如上代码将会以如下方式被进行插入：
void foo(int *p) {
__tsan_func_entry(__builtin_return_address(0));
__tsan_write4(p);
*p = 42;
__tsan_func_exit()
}
另外应用程序的8字节将会拥有N个对应的8字节shadow空间，用于记录每次内存访问的相关信息：
○ ~16 bits: TID (thread ID)
○ ~42 bits: Epoch (scalar clock)
○ 5 bits: position/size in 8-byte word
○ 1 bit: IsWrite
如上T1访问的8字节中的0-2字节，T3访问的是0-4字节，存在交集，因此需要判断它们两个是否存在happens-before关系，如果不存在就报告竞争。
4.7.DYNAMIC ANNOTATIONS
任何的动态竞争检测器必须要理解测试程序所使用的同步机制，否则是无法正确工作的。对于那些只使用了POSIX mutex的程序来说，可以直接将关于POSIX API的知识hardcode到检测器中。但是如果测试程序采用了其他的同步方式的话，需要将其解释给检测器。为此Tsan提供了一组Dynamic Annotations–一种竞争检测API，每一个annotation都是一个C宏定义。通过采用Dynamic Annotations，可以让Tsan理解我们自己实现的同步机制。
并不是所有的程序都可以方便地采用竞争检测器进行检测。如果要编写对竞争检测器友好的程序，需要开发者遵循如下几个建议(其中有些已经过时，比如原子操作，随着工具的改进，它会逐步增加一些新的支持)：
1. 首先，线程间的共享变量最好是都采用mutex进行保护，只有在真正存在严重性能问题的情况下才考虑选择采用其他方式。
2. 在可能的情况下，尽量复用现有的标准同步方式(比如消息队列，引用计数)而不是重复造轮子。如果真的需要自己的同步机制的话，也要通过Dynamic Annotations进行注释。
3. 避免直接使用条件变量，因为它们对于hybrid模式的检测器是不友好的。而是应该将它们封装到独立的函数中，并进行annotae。
4. 避免直接使用原子操作，而是将它们封装成实现了某一同步模式的类或函数中。
5. 切记动态检测速度很慢，不要将任何的timeout值hardcode到代码中，确保它们是可配置的
6. 永远都不要使用sleep()作为线程间同步机制，即使是在ut中也不要这么做
7. 不要过度同步。
5.MemorySanitizer
http://llvm.org/devmtg/2013-04/stepanov-slides.pdf
该工具也是Google开发的，但是目前还没有移植到GCC，未来估计也会移植到里面。所以这里也简要介绍一下。
http://code.google.com/p/memory-sanitizer/
它是用来检测读取未初始化内存的错误的。与Valgrind (Memcheck tool)相比，它的优势就是采用的是CTI(编译时插入)，由此带来非常少的性能损失。使用MemorySanitizer，原始程序性能大概会降低1.5x-2.5x，而Valgrind 则可能降低20X。
6.工具比较
Comparison of various memory error detectors
Comparison of binary translation systems
AddressSanitizer最突出的特点就是采用CTI(编译时插入)技术运行速度快，可以检查出栈与全局对象的越界访问。
Comparison of ThreadSanitizer, Helgrind, Drd and Intel Thread Checker
Links related to race detection
http://oss-security.openwall.org/wiki/tools
ThreadSanitizer最突出的特点也是采用CTI(编译时插入)技术运行速度快，另外输出信息详细方便快速定位问题，支持Dynamic Annotations，同时支持hybrid和纯happens-before模式。
对于一个检测工具来说，快是一个非常关键的feature，只有足够快才好放到daily的回归测试甚至是在线上打开，如果性能开销太大的话另外很多问题尤其是多线程问题可能根本不会在检测时复现。比如Tsan和Asan都要比Valgrind快一个数量级。当然与Valgrind先比，它们也有需要重新编译源代码的缺点。
7.其他参考资料
http://llvm.org/devmtg/2012-11/Serebryany-ASAN-TSAN-Poster.pdf
http://llvm.org/devmtg/2012-11/Serebryany_TSan-MSan.pdf
Debugging Memory Bugs Using Address Sanitizer