技术

Valgrind笔记（二）：MemCheck基本原理

Valgrind的MemCheck工具，可以检测多种内存错误，它是如何做到的？

V bits

MemCheck构造出一个“虚拟CPU”。与真实CPU不同的是，虚拟CPU中的每一个bit，都有一个关联的“是否有效”bit（ “valid-value” bit），用于表示它关联的bit是否有效（更确切地，应该是“是否初始化”）。以下称这个bit为V bit。

例如，当CPU从内存中加载一个4-byte int时，也同时从V-bit位图中加载32bits的V bits。当CPU把这个int写回某个地址时，这32bits的V bits也会被存回V-bit位图中。

也就是说，系统中的所有bits，都有对应的V bits。不仅仅是内存，甚至是CPU寄存器，也有它们的V bits。为了实现这样的功能，MemCheck需要为V bits提供强大的压缩能力。

仅仅是访问非法的数据，并不会直接触发MemCheck的报错。仅当这一错误影响到程序的执行结果时，才会报错。例如：

1
2
3
4
5
6
int i, j;
int a[10], b[10];
for ( i = 0; i < 10; i++ ) {
    j = a[i];
    b[i] = j;
}

虽然访问a[i]时，未初始化，但是它并不会报错。因为这段程序仅仅是把未初始化的a[10]复制到b[10]。并没有把这些未初始的值用于某种判断或输出。如果程序改为：

1
2
3
4
5
6

for ( i = 0; i < 10; i++ ) {
    j += a[i];
}
if ( j == 77 ) 
    printf("hello there\n");

MemCheck就会报错了。未初始化的值a[i]之和，被用于计算j并用于判断if (j == 77)。

在CPU做各种运算时（加，位运算等），操作数的V bits被引用，用于计算出运算结果的V bits。但是，即使这里包含非法的V bits，MemCheck仍然不会报错。仅当以下几种情况发生时，MemCheck才会去检查V bits的有效性：

  • 运算结果被用于生成地址
  • 影响程序控制流（如条件判断）
  • 有系统调用发生

这样的机制似乎看起来过度设计了，但一旦联想到C语言中有一个常见的机制叫“结构体自动填充”，你就不会这么觉得了。以下这个例子：

1
2
3
4
5
6
struct S { int x; char c; };
struct S s1, s2;
s1.x = 42;
s1.c = 'z';
s2 = s1;
if (s2) printf("s2\n");

请问，以上代码中，是否有未初始化的赋值？答案是：有。struct S在除了x和c成员外，还有3 bytes的自动填充字段，而这部分字段是未被初始化的。作为C语言程序员，想必你不会希望MemCheck因未初始化的自动填充字段而报错。

A bits

在MemCheck构建的“虚拟CPU”之上，对应每一个数据，除了V bits外，还有表示地址有效性的Valid-address bits，简称A bits。与V bits不同的是：1）A bits仅仅针对内存中的数据存在，CPU寄存器中的数据，没有A bits。2）每一byte的内存数据，对应一bit的A bit。A bits用于表示程序是否可以合法地读写此地址的数据。

每当程序读写内存时，MemCheck会检查对应地址的A bits。如果A bits指示当前的地方访问是非法的，将抛出告警。此时，MemCheck仅仅会检查A btis，而不会修改它。

A bits是如何被构建出来的呢：

  • 进程启动时，所有全局变量的A bits被标记为“可被访问”。
  • malloc/new时，申请出来的内存，被标记为“可被访问”。它们被free时，该地址修改为“不可访问”。
  • 栈指针（stack pointer register，SP）上下移动时，A bits会被修改。在SP之上，至栈基地址之间的地址，被标记为“可被访问”。SP之下的地址，被标记为“不可访问”。
  • 系统调用时， A bits会被修改。例如：mmap把一段地址映射进进程地址空间，会被标记为“可被访问”。
  • 程序可以主动告诉MemCheck，哪些地址应该被做何种标记。

规则总结

综合A bits与V bits，MemCheck检测内存错误，会遵循以下原则：

  • 内存中的每一byte数据，都有8 bits关联的V bits和1 bit的A bits。V bits表示对应的内存数据是否被初始化；A bits表示程序对此地址空间的访问，是否合法。经过压缩，A bits + V bits通常会增加25%的内存使用。
  • 当内存读写发生时，关联的A bits被取出，用于检查地址访问的合法性。MemCheck在发生非法访问时，会抛出异常。
  • 当内存被读进CPU寄存器时，关联的V bits被读进“虚拟CPU”中；* 当CPU寄存器中的数据被写进内存时，关联的V bits也从“虚拟CPU”中被写回内存中。
  • 当数据被用于生成地址，或会影响程序控制流（如条件判断）时，或数据用于系统调用，V bits被检查。其它情况下，V bits不作检查。当发现使用未初始化的数据，MemCheck会抛出异常。
  • 一旦V bits被检查过，它们就被置为“有效”。这一手段用于避免过多地重复报错。
  • 当数据从内存中加载进CPU时，MemCheck检查 A bits的合法性，在发现非法访问时抛出异常。当发生非法访问时，V bits被强制置为“有效”（尽管A bits为“不可访问”）。这种机制用于避免过多的冗余报错。
  • MemCheck会拦截内存访问接口malloc, calloc, realloc, valloc, memalign, free, new, new[], delete, delete[]，这些接口中发生系统调用时，对应地修改A bits和V bits。

参考文献