Question

为什么C语言检查数组访问越界会这么难

Answer 1

C语言中数组和内存管理，是安全性和性能之间矛盾关系的重要部分。

我曾提到要讨论性能和安全性之间的矛盾。这个矛盾的一个重要部分就是因为C语言中数组和内存管理的本质特征导致的。

理论上，数组是一个简单的数据结构：当你需要访问其中的一个元素时，只需要给出该元素的索引位置，就能对该元素进行读或者写操作。这句话中也隐含了
一个问题，那就是你需要访问一个元素时，都需要提供一个索引位置。使用索引位置来找元素通常是一个代价很高的计算，尤其是当元素的大小不是2的整数次幂
时： 在诸如表达式++a[i], 在地址递增的过程中，其计算地址的代价可以轻松超过5倍于a[i]的地址的代价。

在至少50年的时间里，编译器开发人员一直在努力让访问数组元素变得更快。其中很大一部分的工作都围绕想下面这种循环进行：
for (size_t i = 0; i < n; ++i)
c[i] = a[i] + b[i];

这段代码在每次循环迭代中，都需要通过计算将三个索引地址转换成对应的内存位置中，这种计算也带入了一些开销。 许多编译器都通过将循环重写为如下代码的方式来实现高效计算。在这段代码中，我们假设Pointer类型是可以指向a,b,c三个数组中某个元素的指针。
Pointer ap = &a[0], bp = &b[0], cp = &c[0], aend = ap + n;
while (ap < aend) {
*cp++ = *ap++ + *bp++;

}

这段转换后的代码将三个数组索引计算操作转换成了三个地址加操作，这样加速显著。不过，这个简单的转换操作看起来容易，做起来却很复杂，
因为编译器需要能够确认在这个for循环体中没有对i值本身的修改。 上面的例子可以很直观的看到i不会被改变，不过在实际的代码中，往往要困难很多。

C语言与在它之前的编程语言相比，一个非常重要的不同就是C能提供给程序员一些直接优化代码的机会，而不是简单的依赖编译器去做优化。C语言通过将数组和指针的概念统一化，使得程序员可以自己做大部分的数组索引计算，而在C语言之前，这些工作只能通过编译器去做。

用手动计算索引取代自动计算是一种进步，这个听起来有点怪怪的。但是在实际编程中，可能很多程序员都宁愿手工优化代码，而不是依赖编译器自动优化，因为无法确定编译器到底对代码做了什么。这也可能是吸引C程序员使用指针而不是索引来访问数组元素的原因之一。

除了在很多情况下会更快外，指针相比数组还有另外一个很大的优势：可以只用指向数组中特定元素的一个指针来识别数组中的元素。比如，假设我们想写一

个函数来对数组中某个区域内的元素做操作。如果没有指针，我们需要三个参数来确定这个区域：数组名称，区域开始索引，区域结束索引。而如果使用指针的话，
只要两个参数就足够了。

此外，不管是动态分配的内存，还是其他内存地址，都可以统一使用指针。例如，在malloc库函数返回一个指向动态内存的指针后，我们可以用这个指

针创建任何我们需要的数据结构。一旦我们在这块动态分配的内存中创建了这些数据结构之后，我们就能使用指向这些数据结构某个部分的指针来让其他函数可以直
接访问这一部分数据。 相应的，这些函数也无需知道他们将使用的内存到底是什么性质的。

使用指针是方便了很多，但是也要付出代价的。相比于使用索引变量引用数组元素的表示形式，使用指针的表示形式将会引入三种潜在危害。

第一，因为指向数组元素的指针和数组本身是完全独立的。
因此，在数组不存在或者内存释放之后，指针仍然有可能存在。比如，我们将数组元素的地址
&a[0]保存到指针ap中，我们同时也引入了在a不存在的时候，使用*ap的风险。这种风险在完全使用数组加索引的形式中是不存在的，因为一旦
数组a消失了，我们也无法引用他的元素。

第二，指针运算的可行性。
如果我们使用一对指针指向一个数组区间的两端，那么我们就一定能找到其中间元素的位置，因为可以直接使用数学运算得到。但
是这种指针的数学运算也同时引入了很多制造不可用地址的可能性，而且这种通过数学运算得到的不可用地址， 相比简单的一些针对整数的数学运算来说，
更难检测到。

最后，使用指针来表示范围，不仅仅需要指针本身存在且可用，还需要指针指向的内存是可用的内存
。上面代码中的aend变量就是一个典型例子。我们创
建了一个aend变量，并用它指向循环的上界。但是如果我们想试图对*aend取值，结果将是未定义的。这类指针被称为off-the-end指针。这类
指针的存在，也让验证C语言是否存在越界错误变得非常困难。