技术

从汇编的角度理解程序（四）—— 复杂数据结构

这篇文章是我《从汇编的角度理解程序》系列的第四篇。
在前面的三篇文章里，第一篇文章介绍了寄存器和按顺序执行的汇编指令，第二篇文章分析了按顺序执行的指令如何通过跳转实现分支和循环，第三篇文章分析了如何借助寄存器和栈内存实现有复杂状态的函数调用。
这一篇文章将会分析如何通过规范的内存布局和访问规则实现复杂的数据结构——数组(array)、结构体(struct)和联合(union)。

一、如何实现 Array

1.1 先从简单的 1 维数组开始

在分析函数栈帧的时候提到一种基于 %rsp + offset 来访问数据的方法，Array 数据结构使用了类似的思想。
对于元素类型为 T 且长度为 N 的数组 T A[N]，程序会申请恰好 sizeof(T) * N bytes 的连续内存用来保存所有元素的数据，并把这块内存的起始位置保存在 A 上。而汇编指令只需要由 A 一个数据加偏移就能访问到数组里面的所有数据。
你可能会好奇元素的类型(T)信息保存在哪里。实际上 T 信息没有保存，只是在编译期间根据 T 来决定偏移的步长以及寄存器的位数。
假如 A 的值 P 保存在 %rdi 上，i 保存在 %rsi 上，元素类型为 int，要返回 A 的各种表达式的值，其所对应的汇编指令如下表所示：

表达式 获取的数据类型 获取的数据值 汇编指令
A int* P movq %rdi, %rax
A[0] int M[P] movq (%rdi), %rax
A[i] int M[P + 4i] movq (%rdi, %rsi, 4), %rax
&A[1] int* P + 4 leaq 4(%rdi), %rax
A + i - 1 int* P + 4i - 4 leaq -4(%rdi, %rsi, 4), %rax
*(A + i - 2) int M[P + 4i - 8] movq -8(%rdi, %rsi, 4), %rax
&A[i] - A long i movq %rsi, %rax
这种实现方式依赖于严格依赖于两点规范：
  • 连续且紧凑的内存布局
  • 符合元素字节大小的寻址偏移步长

1.2 从 2 维到多维数组

形如 T A[M][N] 的二维数组，其实现方式在思路上没有什么不同，仍然依赖于上述的内存布局和寻址偏移规范。
T A[M][N] 可以看做以下等价声明：

1
2
typedef T row[N];
row A[M];

也就是以 T A[N] 为 1 行 N 列，共有 M 行。
从内存布局上来说， 1 维数组 T row[N] 就是连续的恰好 sizeof(T) * N 字节的内存， 每个 T 的内存紧凑在一起，一共 N 个 T。
row A[M] 意思为 M 个 row，那么就是连续的恰好 sizeof(row) * M 字节的内存，每个 row 的内存紧凑在一起，一共 M 个 row(行优先)。
至于寻址方式的话，我们发现虽然二维数组的元素是数组，但是这些数组元素之间内存仍然是紧凑的，没有保存数组元素本身(row)的信息。再加之“行优先”的规则，我们可以推导出A[m][n] = A + sizeof(T) * N * m + sizeof(T) * n。
至于 3 维乃至更高维，可以把高维降维到 2 维，在“行优先”和以元素 T 为偏移步长的前提下寻址。
编译器有时会根据对数组的访问逻辑而对寻址算法进行优化。比如 int matrix[m][n] 的访问方式为总是为 matrix[0][n]...matrix[1][n]...matrix[2][n]，它可能会先求出 matrix[0][n] 的地址 col, 然后通过 col+1 访问 matrix[1][2]，等等。

二、如何实现 Struct 和 Union

2.1 如何实现 Struct

Struct 类似 Array，都是基于首字节加偏移的方式访问数据，不过后者保存的是同样类型的元素，前者保存的是不同的数据结构。以下面的程序为例：

1
2
3
4
5
6
struct point {
    int x;
    int y;
    float data[2];
    double radius;
}

形如 point p 会申请 2 个 int(4*2)、2 个 float(4*2) 和 1 个 double(8) 所需的内存 24 字节，p.x 保存在 (&p) 起始的 4 字节中，p.y 保存在 (&p)+4 起始的 4 字节中。p.data 看似一个指针 float*，实际上仍然是保存了两个 float，分别在 (&p)+8 和 (&p)+12。最后， p.radius 保存在 (&p) + 16 起始的 8 字节中。

变量 x y data[0] data[1] radius
起始字节 (&p) + 0 (&p) + 4 (&p) + 8 (&p) + 12 (&p) + 16

假如 &p 保存在 %rdi, 要实现 p.y = p.x，则汇编指令为:

1
2
3
// 汇编，&p 保存在 %rdi
movl (%rdi), %eax
movl %eax, 4(%rdi)

2.2 内存对齐

Struct 和 Array 还有一个不同，后者元素的内存是紧凑分布的，而前者可能会填充空余字节以对齐内存地址。对齐的目标一般是 2/4/8 的倍数，这样是为了优化 CPU 从内存读取数据的性能。
被对齐的对象是 Struct 内的每个元素的基本数据类型，对齐的目标是不小于当前偏移数的最小的基本数据类型的大小的倍数。举例来说：

1
2
3
4
5
6
7
struct s1 {
    int a;
    char b[2];
    double c;
    char d;
}

s1 每个变量的内存布局原本是 0-3/4/5/6-13/14，但是 c 应该对齐到不小于 6 且最小的为 8 的倍数的位置，也就是 8，因此内存布局就成了 0-3/4/5//8-15/16。
然而考虑 s1 arr[2] 的声明，按上述方法两个 s1 的内存布局为 0-3/4/5//8-15/16、17-20/21/22//25-32，第 2 个 s1 的内存明显没有对齐。怎么办呢？
如果要对齐 s1.a, 就要把第 2 个元素的偏移移动到大于 16 的最小 4 的倍数上，也就是 20，于是内存布局变成了 0-3/4/5//8-15/16、20-23/24/25//28-35/36。这个时候仍然有问题，因为 s1.c 的地址为 28，不是 8 的倍数。
为了解决这个问题，我们补充一个新规定：规定结构体的第 1 个元素的地址必须为结构体内最大元素的类型大小的倍数。根据新规定，第 2 个结构体的起始位置就成了 24。
为什么这样是正确的呢？因为基础数据类型的大小是成倍数的，是 8 的倍数的地址，肯定也是 4 的倍数的地址。只要满足了首地址对齐了最大的数据类型，最小的数据类型也就对齐了。
同时，为了满足补充规定，我们把填充的空间放在每个结构体的结尾，而不是开头。也就是说，上述 arr 的内存布局是: 0-3/4/5//8-15/16/+、24-27/28/29//32-39/40/+++。

2.2 如何实现 Union

Union 和 Struct 的区别在于，后者每个成员分配一段内存，总内存为每个成员内存大小之和(不考虑对齐的情况)，前者所有成员共享内存，总内存为数据类型最大的成员所需大小(不考虑对齐的情况)。

1
2
3
4
union u {
    double d;
    unsigned u[2];
}

如上的 Union 只会分配 8 bytes 的内存，u.d 和 u.u 共享这 8 bytes。如果这段内存为 0-8, 则 u.u[0] 的内存为 0-3, u.u[1] 的内存为 5-8，而 u.d 的内存为 0-8。
如果是在小端机器上的话，0-3 为 u.d 的低有效位，5-8 为 u.d 的高有效位。
考虑以下 Union：

1
2
3
4
5
6
7
8
9
10
11
12
union {
    struct {
        long a;
        short b;
        char c;
    } t1;

    struct {
        int d[2];
        char *e;
    } t2;
} f;

如果 f 首地址保存在 %rdi, 要复制 f.t2.d[f.t1.a] 到 %rsi, 则需要如下操作：

1
2
3
// 汇编, &f in %rdi, 复制到 %rsi
movq (%rdi), %rdx
movq (%rdi, %rdx, 4), %rsi

Union 同样遵守内存对齐的规则。

三、总结

复杂的数据结构总是由基本的数据结构组合而成，编译器根据基本数据元素的大小分配内存，基于首字节的偏移来寻址复杂数据结构中的基本元素。
基本数据元素的类型和内存对齐的规则决定寻址偏移的大小，基本元素的数据类型信息本身并没有保存在复杂数据结构中，但是反应在所使用的寄存器位数上。