编程

（C语言）变长数组的陷阱

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

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

相比于固定尺寸，它会生成更多的、并且更慢的代码（而且很脆弱）。

― Linus Torvalds, Linux内核邮件列表

这篇文章的批评主要针对自动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;
}
C

你可以发现，这段代码从用户的输入读取数组长度。编译并且跑一下试试，看看在堆栈溢出造成区块错误（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;
}
C

在这个例子里我可以最大输入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

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

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

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

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

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

意外创建

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

1
2

const int n = 10;
int A[n];
C

好在只要是个比较现代的编译器都会发现并且把这个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]);
    }
}
C

处于介绍的目的，在这个例子中-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"
X86ASM

而无aVLA的版本则生成：

1
2
3
4
5

push    r12
push    rbp
push    rbx
sub     rsp, 4000      ; this is caused by array definition
mov     r12d, edi
X86ASM

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

但是这些区别影响很大吗？是的，很大。

无法初始化

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

1
2

int n = 10;
int A[n] = { 0 };
C

即便开了优化，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] = ... */ }
C

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

1

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

你需要

  • 打破这个习惯
    1

    void foo(int n, int m, int arr[n][m]) { /* arr[i][j] = ... */ }
    C
  • 或者使用过时的语法（即将被标准删除）
    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] = ...
}
    C

结论

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

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

  1. 这是一个歇后语：footgun ↩︎

© 2017 - 2024 JacobZ
使用 Hugo 构建
主题 Stacked 由 Jimmy 设计，Jacob 修改