变长数组在栈上的内存分布

在编译期间,编译器会计算出一个函数中的所有局部变量需要使用多少的内存.这段内存称为函数的栈.

在执行一个函数的时候,会在两个寄存器中分别存有两个指针.

  1. 栈底指针,指向这段内存的起始位置.在riscv指令集,这个指针通常存在寄存器s0中.

  2. 栈顶指针,指向这段内存的结束位置.在riscv指令集,这个指针通常存在寄存器sp中.

这个栈是从高地址往低地址数的,也就是说栈顶指针的值其实比栈底指针小.他们的关系是

栈底指针 - 栈大小 = 栈顶指针

假如有函数fun1()调用了fun2().

那么当执行到fun2()的时候,fun2()的栈底指针等于fun1()的栈顶指针.

也就是有这样的关系(假设fun1的栈底指针是x):

地址 含义
x fun1的栈底指针
x-fun1的栈大小 fun1的栈顶指针
x-fun1的栈大小 fun2的栈底指针
x-(fun1的栈大小+fun2的栈大小) fun2的栈顶指针

疑惑

变长数组存储在哪

我在刚学习编译原理的时候,错误地认为每个栈的大小都是在编译期就已经计算好固定了的.

所以我一直对C99的变长数组感到疑惑.

如果栈的大小是编译期确定的,也就是变长数组不能存储在栈上,那么它在哪?

如果变长数组位于栈上,那么它在栈上是怎么分布的,如何被计算出来?难道是在运行期间才能确定栈的大小吗?

为什么编译器翻译出来的汇编常常使用栈底指针来表示变量的地址

如果我们阅读汇编代码,会发现编译器翻译出来的汇编代码常常使用栈底指针+偏移的方式来指出栈上变量的位置.

只有在刚进入函数的时候,会用栈顶指针+偏移的方式保存上一个函数的信息到当前栈上.

我曾经非常困惑,如果统一使用栈顶指针+偏移不是更加便于理解吗?

结论

通过对变长数组的汇编代码的阅读, 我发现:

  1. 变长数组确实在栈上.
  2. 栈的大小会在运行期改变.这个时候会修改栈顶指针.
  3. 编译器在翻译的时候会先计算栈的大小x(这个大小不包含变长数组).最初进入函数时,会先分配一个大小为x的栈.
  4. 刚进入函数时,栈顶指针 = 栈底指针 - x
  5. 分配了这个大小为x的栈之后,会计算变长数组的大小y.然后直接以新的栈顶指针为变长数组的起始位置,向后再扩张y字节的内存.
  6. 最终,栈顶指针 = 栈底指针 - (x + y)
  7. 栈底指针在这个过程中保持不变,因此我们可以一直用栈底指针来找到栈上变量.

也就是:

地址区间 内容
[栈底指针-x, 栈底指针) 函数中所有的局部变量(不包含变长数组)
[栈底指针-(x+y), 栈底指针-x) 函数中的局部变长数组(此时的地址区间[栈顶指针,栈顶指针+元素大小)是第0个元素的位置)

汇编句读

C语言

一开始我们写下这样的C程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int fun(int x)
{
int a[x];
a[x-1] = 1;
return a[x-1];
}

int main()
{
int x;
scanf("%d", &x);
fun(x);
return 0;
}

汇编

如果使用命令riscv64-linux-gnu-gcc a.c -S -O0生成a.s文件,会发现这个文件里有一些让人难以理解的无用计算(计算的结果直接被覆盖,没有用于任何用途).

例如这一段,大概可以猜测这里做了一个128位的乘法,但是计算出来的结果直接被覆盖.

1
2
3
4
5
6
7
8
9
10
11
12
13
# 如果元素大小位2的k次方字节,那么这些数字将会是61-k, 3+k, k
srli a0,t1,59 # a0 = t1 >> 59 取t1(也就是数组长度x)的最高5位,保存到a5的最低5位上
slli a3,t2,5 # a3 = t2 << 5 取t2(也就是0)的最低59位,保存到a3的最高59位上
or a3,a0,a3 # a3 = a3 | a0 将上面a5(最低5位有值)和a3(最高59位有值)组合起来,形成一个64位数字
slli a2,t1,5 # a2 = t1 << 5 取t1(也就是数组长度x)的最低59位,保存到a2的最高59位上
mv a3,a1 # a3 = a1 a3被数组长度x覆盖?
mv a6,a3 # a6 = a3
li a7,0 # a7 = 0
srli a3,a6,59 # a3 = a6 >> 59 取a6(也就是数组长度x)的最高5位,保存到a3的最低5位上
slli a5,a7,5 # a5 = a7 << 5 取a7(也就是0)的最低59位,保存到a5的最高59位上
or a5,a3,a5 # a5 = a3 | a5 将上面a3(最低5位有值)和a5(最高59位有值)组合起来,形成一个64位数字
slli a4,a6,5 # a4 = a6 << 5 取a6(也就是数组长度x)的最低59位,保存到a4的最高59位上
mv a5,a1 # a5 = a1 a5被数组长度x覆盖?

如果使用命令riscv64-linux-gnu-gcc a.c -S -Og生成a.s文件,产生的汇编就会精简这些意义不明的运算,同时又不会过于精简.

所以下面我们使用加上-Og选项的汇编来讲解.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# 文件的信息:
.file "a.c"
.option pic
# fun1的描述信息:
.text
.align 1
.globl fun
.type fun, @function
# fun1的汇编:
fun:
addi sp,sp,-32
sd ra,24(sp)
sd s0,16(sp)
addi s0,sp,32
la a4,__stack_chk_guard
ld a5, 0(a4)
sd a5, -24(s0)
li a5, 0
slli a5,a0,2
addi a5,a5,15
andi a5,a5,-16
sub sp,sp,a5
addiw a0,a0,-1
slli a0,a0,2
add a0,sp,a0
li a5,1
sd a5,0(a0)
ld a3, -24(s0)
ld a5, 0(a4)
xor a5, a3, a5
li a3, 0
bne a5,zero,.L4
li a0,1
addi sp,s0,-32
ld ra,24(sp)
ld s0,16(sp)
addi sp,sp,32
jr ra
.L4:
call __stack_chk_fail@plt
# fun1的描述信息:
.size fun, .-fun
.section .rodata.str1.8,"aMS",@progbits,1
.align 3
# 字符串"%d"的信息:
.LC0:
.string "%d"
# main的描述信息:
.text
.align 1
.globl main
.type main, @function
main:
addi sp,sp,-32
sd ra,24(sp)
sd s0,16(sp)
la s0,__stack_chk_guard
ld a5, 0(s0)
sd a5, 8(sp)
li a5, 0
addi a1,sp,4
lla a0,.LC0
call __isoc99_scanf@plt
lw a0,4(sp)
call fun
ld a4, 8(sp)
ld a5, 0(s0)
xor a5, a4, a5
li a4, 0
bne a5,zero,.L8
li a0,0
ld ra,24(sp)
ld s0,16(sp)
addi sp,sp,32
jr ra
.L8:
call __stack_chk_fail@plt
# main的描述信息:
.size main, .-main
.ident "GCC: (Ubuntu 11.2.0-16ubuntu1) 11.2.0"
.section .note.GNU-stack,"",@progbits

我们摘出fun1()的内容来看:

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
fun:
addi sp,sp,-32
sd ra,24(sp)
sd s0,16(sp)
addi s0,sp,32
la a4,__stack_chk_guard
ld a5, 0(a4)
sd a5, -24(s0)
li a5, 0
slli a5,a0,2
addi a5,a5,15
andi a5,a5,-16
sub sp,sp,a5
addiw a0,a0,-1
slli a0,a0,2
add a0,sp,a0
li a5,1
sw a5,0(a0)
ld a3, -24(s0)
ld a5, 0(a4)
xor a5, a3, a5
li a3, 0
bne a5,zero,.L4
li a0,1
addi sp,s0,-32
ld ra,24(sp)
ld s0,16(sp)
addi sp,sp,32
jr ra
.L4:
call __stack_chk_fail@plt

第一次分配栈内存

首先,一进入函数就执行以下指令为栈分配了32字节的空间.并且保存了上一级函数的信息

1
2
3
4
addi	sp,sp,-32   # sp = sp - 32  栈顶向下扩展32字节, 32字节是一个预计的大小,
sd ra,24(sp) # *(sp+24) = ra 保存返回地址到[sp+24, sp+32), 也就是将来的[s0-8, s0)
sd s0,16(sp) # *(sp+16) = s0 保存上一级函数的栈底指针到[sp+16, sp+24), 也就是将来的[s0-16, s0-8)
addi s0,sp,32 # s0 = sp + 32 计算出当前函数的栈底

目前栈上的内存如下:

位置 内容
[s0-8,s0) 返回地址
[s0-16, s0-8) 上一级函数的栈底指针
[sp, s0-16) 未使用

设置栈溢出标记

1
2
3
la	a4,__stack_chk_guard    # 取出栈溢出标记的地址,放到寄存器a4
ld a5, 0(a4) # 取出存放在a4中的地址所指向的8个字节内容,存到a5
sd a5, -24(s0) # 将a5中的标记保存到[s0-24,s0-16),

详情见另一篇文章stack_chk_guard避免栈溢出攻击

目前栈上的内容如下:

位置 内容
[s0-8,s0) 返回地址
[s0-16, s0-8) 上一级函数的栈底指针
[s0-24, s0-16) 栈溢出标记
[sp, s0-24) 未使用

计算变长数组大小

1
2
3
4
li	a5, 0           # a5 = 0
slli a5,a0,2 # a5 = a0 << 2(相当于a5=a0*4) 计算出数组大小,每个元素4字节
addi a5,a5,15 # a5 = a5 + 15
andi a5,a5,-16 # a5 = a5 & (-16) 这两步是一个位运算的技巧,作用是将a5变为16的倍数(向上取整)

这里的寄存器a0保存了参数x,这是riscv函数调用的习惯.

计算出数组的大小按照16字节对齐.

第二次分配栈内存

1
sub	sp,sp,a5    # sp = sp - a5 

栈顶指针再向下扩张a5个字节的大小.

目前栈上的内容如下:

位置 内容
[s0-8,s0) 返回地址
[s0-16, s0-8) 上一级函数的栈底指针
[s0-24, s0-16) 栈溢出标记
[sp+数组大小, s0-24) 未使用
[sp, sp+数组大小) 变长数组

操作变长数组

1
2
3
4
5
addiw	a0,a0,-1    # a0 = a0 - 1 32位加法,计算x-1
slli a0,a0,2 # a0 = a0 << 2(相当于a5=a0*4) 计算出第x-1个元素相对于数组起点的偏移
add a0,sp,a0 # a0 = sp + a0 计算出第x-1个元素的地址,也就是[sp+a0,sp+a0+元素大小)
li a5,1 # a5 = 1
sd a5,0(a0) # *(a0) = a5 给第x-1个元素赋值

检查栈溢出标记

1
2
3
4
5
ld	a3, -24(s0)     # 取出之前的标记
ld a5, 0(a4) # 获取一个新的标记
xor a5, a3, a5 # 将原本的标记和新的标记对比,从而检查就标记是否被修改
li a3, 0
bne a5,zero,.L4 # 如果被修改,那么跳转到.L4

可以认为地址__stack_chk_fail@plt存有一个处理检查异常的函数.

一旦检查不通过就会调用他来处理.

1
2
.L4:
call __stack_chk_fail@plt

返回

1
2
3
4
5
6
li	a0,1            # a0 = 1
addi sp,s0,-32 # sp = s0 - 32 恢复第一次分配栈内存时的sp
ld ra,24(sp) # 取出之前保存的返回地址
ld s0,16(sp) # 取出之前保存的上一级函数的栈底地址
addi sp,sp,32 # 恢复sp指针到进入函数之前
jr ra # 跳转到回上一级函数

变长数组在栈上的内存分布
https://zzidun.tech/2d6cc7c5/
作者
zzidun pavo
发布于
2022年8月6日
许可协议