(C 语言)变长数组的陷阱

前言

这篇文章转载自 Jorengarenar 的博客。类似于前一篇文章,这一篇博文是我在搜索为什么 Rust 不支持动态栈分配的时候看到的。有很多人希望 Rust 支持变长数组,并且有一个相关的 RFC,但是也有人提到这很危险,并且不会带来太大的收益,这篇文章总结了变长数组的问题,可供参考。

正文

相比于固定尺寸,它会生成更多的、并且更慢的代码(而且很脆弱)。—— Linus Torvalds

VLA 是变长数组(variable-length array)的缩写,它指的是长度在运行时而不是编译时决定的数组(真・数组,而不是接口像数组的一块内存)。VLA 在 C99 标准中被引进,乍看上去它很方便并且高效,但是这只是各幻觉,实际上它只是一些顽固问题的源头。

这篇文章的批评主要针对自动变长数组(automatic VLA),而不是所有形式的 VLA,因此我在后文会用缩写 aVLA 来进行区分。

支持某种形式的 VLA 的语言有:Ada, Algol 68, C, C#, COBOL, Fortran, J 和 Object Pascal。你可能注意到了,除了 C 和 C# 之外,其他的语言都不主流了。

你从开头的引言中可能也猜到了,一个相当依赖于 VLA 的项目不是别的,正是 Linux 内核。维护者们花费了很多精力来移除 VLA,并且在内核版本 4.20(2018 年)后实现了完全无 VLA。

在这篇文章刚开头的时候,我还要指出,在一些情形下,VLA 是一个好解决方案。这样的情形不多,但是确实存在。未来我会尽力好好介绍他们并且链接到这篇文章来。

栈分配

aVLA 通常分配在栈上,这就绝大部分问题的根源。我们来看一个非常简单并且看起来很适合 aVLA 的例子:

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void) {
int n;
scanf("%d", &n);
long double arr[n];
printf("%Lf", arr[0]);
return 0;
}

你可以发现,这段代码从用户的输入读取数组长度。编译并且跑一下试试,看看在堆栈溢出造成区块错误(segfault)前,你可以输入多少值。在我的测试里这个上限是 50 万。这只是一个基础数据类型!想象以下对于一个结构体这个上限可能是多少!或者如果不仅仅是 main()?考虑下递归函数?这个上限会大幅降低。

并且,你没有任何(可移植、标准)的方法来处理堆栈溢出 —— 你的程序已经无可救药地崩了。因此你要么需要在声明数组之前进行严格的长度审查,要么指望用户不要输入太大的数据。(这样赌博的后果显而易见)

因此程序员必须保证 aVLA 的商都不能超过安全的上限。但是实际情况里,如果你知道这个安全上限,那没道理你不会去确认它。

最糟糕的是

最糟糕的是 segfault 只是不当使用 aVLA 造成的后果中最好的一个。最坏情况是造成可以被利用的漏洞,攻击者可能会选择一个值,使得这个数组与其他内存分配重叠,从而控制那些值。这是个安全性灾难。

如果你接受(进一步)损失程序性能,在 GCC 中你可以开启 -fstack-clash-protection 选项,它会在进行变长栈空间分配时,增加额外的指令来在每个内存页上进行探测。这可以确保所有的栈分配是有效的,或者在无效的时候抛出 segfault,来缓解栈冲突(stack-clash)问题,从而将可能的代码执行攻击变成服务拒绝(denial of service)

那如何修改这个例子?

如果我想让用户决定数组大小并且创建大的离谱的定长数组很浪费?很简单,用 malloc()

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>

int main(void) {
int n;
scanf("%d", &n);
long double* arr = malloc(n * (sizeof *arr));
printf("%Lf", arr[0]);
free(arr);
return 0;
}

在这个例子里我可以最大输入 13 亿而不让我的机子报错。这大概是之前的 2500 倍!但是我最后仍然会碰到 segfault 是吧?唔,区别在于我们可以检查 malloc() 的返回值,然后比如我们就可以告知用户:

1
2
3
4
long double* arr = malloc(n * (sizeof *arr));
if (arr == NULL) {
perror("malloc()"); // output: "malloc(): Cannot allocate memory"
}

我碰到过相左的观点:C 经常被用于系统和嵌入式的语言,这些情况下可能都没法使用 malloc()

唉。。看来我又要重复一遍了,不过这确实很重要。

在这种设备上你同样也没有多少栈空间。因此相比于在栈上动态分配空间,你应该确定你到底需要多少内存然后只使用固定尺寸的内存。

当在栈空间很小的设备上使用 aVLA 的时候,你很容易弄出一些看起来能用的东西,但是当你的函数在栈已经很深的,有很多数据的时候被调用,你的栈就会炸。

如果你在每个地方都分配固定尺寸的栈空间,那么你知道这肯定没问题。如果你在栈上动态分配内存,你需要测试你所有的代码路径,并且在所有可能的分配尺寸情况下进行测试,这比前者更难更容易出错。不要在甚至没有好处的情况下让它更容易射到你的脚(一个歇后语:footgun)

意外创建

不像其他危险的 C 语言特性,aVLA 没有什么门槛。很多新手会在试错之后开始使用这个特性,却根本不了解它的问题。有些时候甚至很有经验的程序员都会大意,在不需要 aVLA 的时候创建它。以下就是一个完全没必要的静静地创建了一个 aVLA 的例子:

1
2
const int n = 10;
int A[n];

好在只要是个比较现代的编译器都会发现并且把这个 aVLA 给优化掉,但是。。。万一它没发现呢?或者它处于某种原因(安全?)没有这么做呢?优化没打开呢?但这肯定都问题不大,是吧?呃。。。

比定长慢

在编译器不优化的情况下,之前这个 aVLA 的例子在数组初始化之前会生成 7 倍多的汇编指令,相比于它对应的定长情况(参见 jmp .L5 之前的汇编部分)。但这是没有开编译器优化的情况,如果开了生成的汇编是一模一样的。

这里有一个 aVLA 不是意外插入的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
void bar(int*, int);

#if 1 // 1 for aVLA, 0 for aVLA-free

void foo(int n) {
int A[n];
for (int i = n; i--;) {
scanf("%d", &A[i]);
}
bar(A, n);
}

#else

void foo(int n) {
int A[1000]; // Let's make it bigger than 10! (or there won't be what to examine)
for (int i = n; i--;) {
scanf("%d", &A[i]);
}
bar(A, n);
}

#endif

int main(void) {
foo(10);
return 0;
}

void bar(int* B, int n) {
for (int i = n; i--;) {
printf("%d %d", i, B[i]);
}
}

处于介绍的目的,在这个例子中 -O1 级别的优化是最好的(生成的汇编会更清楚,然后 -O2 并不会有太大的用处)。

当我们编译 aVLA 的版本,在 for 循环之前的指令如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
push    rbp
mov rbp, rsp
push r14
push r13
push r12
push rbx
mov r13d, edi
movsx r12, edi ; here aVLA "starts"...
sal r12, 2 ;
lea rax, [r12+15] ;
and rax, -16 ;
sub rsp, rax ;
mov r14, rsp ; ... and there "ends"

而无 aVLA 的版本则生成:

1
2
3
4
5
push    r12
push rbp
push rbx
sub rsp, 4000 ; this is caused by array definition
mov r12d, edi

因此不仅定长数组生成更少的代码,它也简单多了。为什么 aVLA 在最开始的时候会产生更多的开销?它没有什么特别伟大的任务,但仍然不是简简单单的一个指针移动。

但是这些区别影响很大吗?是的,很大

无法初始化

在 aVLA 不经意间造成的问题中还有如下不被允许的例子:

1
2
int n = 10;
int A[n] = { 0 };

即便开了优化,aVLA 仍然不支持初始化。因此尽管我们想要的是定长数组并且理论上编译器可以干这件事,但它就是行不通。

给编译器作者带来麻烦

几个月前我存了 Reddit 上的一个评论,它列举了从编译器开发者的角度在 VLA 上碰到的问题。我把它引在下面:

  • VLA 其实适用于一个类型,而不是一个实际数组。因此你可以给 VLA 类型加一个 typedef,它会冻结用到的表达式,即便这个表达式的一部分在 VLA 类型被使用的时候已经变了
  • VLA 可以在代码块和循环中使用,这意味着要在栈上分配和释放动态长度的数据,如果你不想让偏移量(offsets)被乱搞,你就需要用指针来间接地实现它。
  • 你可以在有 VLA 被使用的情况下用 goto 跳进或者跳出代码块,有些事情会被限制,但是也有不被限制的,而编译器却需要跟踪所有的这些骚操作
  • VLA 可以被用在多维数组上
  • VLA 可以被指针指向(因此你不需要分配空间,但是仍然需要跟踪所有变量的大小)
  • 有些编译器允许在结构体定义里面使用 VLA(我真的不知道这是怎么弄的,或者在什么地方 VLA 的尺寸被定下来了,然后所有的结构体会拥有同样的 VLA 尺寸)
  • 一个函数可以同时有多个 VLA 被使用,并且它们可以在不同的地方,或者有条件地,或者在循环里被创建或者销毁。
  • sizeof 需要被专门针对 VLA 实现(针对一个 VLA 实体,VLA 类型,混合 VLA 和定长尺寸的类型,VLA 数组,VLA 指针)
  • VLA 这个词还被用于描述(当维数由传入参数确定时)多维数组的参数
  • 在 Windows 上用有些编译器的时候(至少 GCC 是这样),声明过大的局部数组(使得栈尺寸超过 4KB)意味着要调用一个特殊的分配器(__chkstk()),因为栈空间一次只能增长一个内存页)。当声明一个 VLA 的时候,编译器不知道它的长度,因此它需要在每个涉及的函数里都调用(__chkstk()),即便 VLA 的尺寸实际上很小。

并且相信我,如果你在 C 语言的一些论坛里溜一圈,你会发现更多不同的抱怨。

降低可移植性

由于前面提到的这所有问题,有些编译器决定不完全支持 C99。最主要的例子是微软的 MSVC。C 语言标准委员会页注意到了这个问题,并且在 C11 修订版中将 VLA 的支持标为可选的。

C2x 计划将推翻这个决定,但是 aVLA 仍然不是强制的

这意味着使用 VLA 的代码有可能没法被一个 C11 编译器编译。因此你需要检查__STDC_NO_VLA__宏,并且在不支持的时候增加备用选项。

另外,C++ 没有 VLA 并且没有证据表明它有将来会支持。这不是什么大事,但是仍然给 C 的 VLA 提供了一个反例

(挑骨头)打破调用习惯

这是鸡蛋里挑骨头了,但是它确实是另一个让人不喜欢 VLA 的原因。一个常用的函数调用习惯是先传指针,再传参数,对于数组它的意思是:

1
void foo(int** arr, int n, int m) { /* arr[i][j] = ... */ }

C99 标准中,提到数组的长度必须在参数列表里遇到的时候立马被分析确定,这意味着在用 VLA 的时候你没法用跟上面一样的语法

1
void foo(int arr[n][m], int n, int m) { /* arr[i][j] = ... */ } // 非法!

你需要

  • 打破这个习惯
    1
    void foo(int n, int m, int arr[n][m]) { /* arr[i][j] = ... */ }
  • 或者使用过时的语法(即将被标准删除)
    1
    2
    3
    4
    5
    6
    7
    8
    void foo(int[*][*], int, int);
    void foo(arr, n, n)
    int n;
    int m;
    int arr[n][m]
    {
    // arr[i][j] = ...
    }

结论

简而言之,别用 VLA,编译你代码的时候开启 -Wvla 开关。VLA 特性带来了很多危险却经常没有与之匹配的有用的回报。如果你发现在你的使用场景里里 VLA 是一个有效的解决方法,那就用它,但是记住我上面所提到的这些局限。

可能还值得一提的是,VLA 还被认为是解决问题同样很多的,不标准的 alloca() 的一个途径。