目录过程运行时栈转移控制数据传送数组分配和访问异质的数据结构结构联合union读取double的位模式数据对齐过程过程Procedure是软件中的核心抽象机制提供代码封装能力通过指定参数和可选返回值实现特定功能在程序中不同位置可重复调用隐藏具体实现细节提供清晰简洁的接口假设过程P调用过程QQ执行后返回到P这些动作包括下面一个或多个机制。传递控制在进入过程 Q 的时候程序计数器必须被设置为 Q 的代码的起始地址然后在返回时要把程序计数器设置为 P 中调用 Q 后面那条指令的地址传递数据P 必须能够向 Q 提供一个或多个参数 Q 必须能够向 P 返回一个值分配和释放内存在开始时 Q 可能需要为局部变量分配空间而在返回前又必须释放这些存储空间运行时栈**C语言过程调用的一个关键机制在于使用了栈提供的后进先出的内存管理原则。**在过程 P 调用过程 Q 的例子中可以看到当 Q 在执行时 p 以及所有 在向上追溯到 P 的调用链中的过程都是暂时被挂起的。当 Q 运行时它只需要为局部变量分配新的存储空间或者设置到另一个过程的调用。 另一方面当 Q 返回时任何它所分配的局部存储空间都可以被释放。因此程序可以用栈来管理它的过程所需要的存储空间栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息。 当 P 调用 Q 时控制和数据信息添加到栈尾。当 P返回时这些信息会释放掉。之前笔记讲过x86-64 的栈向低地址方向增长而栈指针%rsp 指向栈顶元素。可以用 pushq 和 popq 指令将数据存入栈中或是 从栈中取出。将栈指针减小一个适当的量可以为没有指定初始值的数据在栈上分配空间。类似地可以通过增加栈指针来释放空间。当 x86-64 过程需要的存储空间超出寄存器能够存放的大小时就会在栈上分配空间。这个部分称为过程的栈帧 (stack fram) 。当前正在执行的过程的帧总是在栈顶 。 当过程 P 调用过程 Q 时 会把返回地址压入栈中指明当 Q 返回时要从 P 程序的哪 个位置继续执行 。 我们把这个返回地址当做 P 的栈帧的一部分因为它存放的是与 P 相关的状态 。 Q 的代码会扩展当前栈的边界分配它的栈帧所需 的空间。 在这个空间中它可以保存寄存器的值分配局部变量空间为它调用的过程设置参数 。 大多数过程的栈帧都是定长的在过程的开始就分配好了 。 但是有些过程需要变长的帧。通过寄存器过程 P 可以传递最多 6 个整数值也就是指针和整数但是如果 Q 需要更多的参数 P 可以在调用 Q 之前在自己的栈帧里存储好这些参数 。转移控制将控制从函数 P 转移到函数 Q 只需要简单地把程序计数器(PC)设置为 Q 的代码的起始位置 。从 Q 返回的时候处理器必须记录好它需要继续 P 的执行的代码位置 。 在 x86-64 机器中这个信息是用指令 call Q 调用过程 Q 来记录的。该指令会把地址 A 压入栈 中并将 PC 设置为 Q 的起始地址 。 压入的地址 A 被称为返回地址是紧跟在 call 指令后面的那条指令的地址。对应的指令 ret 会从栈中弹出地址 A, 并把 PC 设置为 A。call 指令有一个目标即指明被调用过程起始的指令地址 。 同跳转一样调用可以是直接的也可以是间接的 。 在汇编代码中直接调用的目标是一个标号而间接调用的目标是 后面跟一个操作数指示符。数据传送当调用一个过程时除了要把控制传递给它并在过程返回时再传递回来外过程调用还可能包括把数据作为参数传递而从过程返回还有可能包括返回一个值。x86-64 中 大部分过程间的数据传送是通过寄存器实现的。x86-64 中函数的前 6 个整型参数含整数、指针通过寄存器传递寄存器使用顺序固定且根据参数大小选择对应寄存器名参数序号64位32位16位8位第1个%rdi%edi%di%dil第2个%rsi%esi%si%sil第3个%rdx%edx%dx%dl第4个%rcx%ecx%cx%cl第5个%r8%r8d%r8w%r8b第6个%r9%r9d%r9w%r9b参数按声明顺序依次分配寄存器小尺寸参数通过 64 位寄存器的低字节部分访问如 32 位参数用 %edi。指针类型统一为 8 字节使用 64 位寄存器如 %rdi、%rsi。整型参数数量超过 6 个时第 7 个及之后的参数通过栈传递。数组分配和访问对于数据类型 T 和整型常数 N, 声明如下 T A[N];起始位置表示为x A x_AxA​。 这个声明有两个效果。首先它在内存中分配一个 L• N 字节的连续区域这里 L 是数据类型 T 的大小单位为字节。其次它引入了标识符 A, 可以用 A 来 作为指向数组开头的指针这个指针的值就是x A x_AxA​。可以用 0~N-1 的整数索引来访问该数 组元素。数组元素 i 会被存放在地址为x A x_AxA​ L• i的地方。访问嵌套的数组要访问多维数组的元素编译器会以数组起始为基地址 可能需要经过伸缩的偏移量为索引 产生计算期望的元素的偏移量然后使用某种 MOV 指令。通常来说对于一个声明如下的数组T D[R][C]它的数组元素D[i][j]的内存地址为D[i][j] x D L ( C ⋅ i j ) x_DL(C\cdot{ij})xD​L(C⋅ij)L 是数据类型 T 以字节为单位的大小。关于变长数组变长数组允许数组的维度是表达式在数组被分配的时候才计算出来。比如变长数组int A[n][n]n 是运行时才知道的所以编译器不能用固定的常数去优化。它必须真的计算A[i][j] xA 4 * (n*i j)对应乘法指令imulq %rdx, %rdi# n * i**地址计算不能全靠移位和加法必须用乘法。**定长数组靠常数优化变长数组靠指针步长优化前者能消掉索引后者通常保留索引。异质的数据结构结构C 语言的 struct 声明创建一个数据类型将可能不同类型的对象聚合到一个对象中。 用名字来引用结构的各个组成部分。类似千数组的实现结构的所有组成部分都存放在内存中一段连续的区域内而指向结构的指针就是结构第一个字节的地址。编译器维护关于 每个结构类型的信息指示每个字段如Id) 的字节偏移。它以这些偏移作为内存引用指令中的位移从而产生对结构元素的引用 。结构体字段没有运行时“名字”编译器只把它看成一块连续内存访问字段就是“基地址 偏移量”。联合联合提供了一种方式能够规避 C 语言的类型系统允许以多种类型来引用一个对象。联合声明的语法与结构的语法一样只不过语义相差比较大。它们是用不同的字段来引用相同的内存块 。有如下声明structS3{charc;inti[2];doublev;};unionU3{charc;inti[2];doublev;};字段的偏移量、数据类型 S3 和 U3 的完整大小如下类型civ大小S3041624U30008偏移 0: c (1 字节)偏移 1-3: padding (3 字节填充为了让 i 对齐到 4 字节边界)偏移 4-11: i[0], i[1] (8 字节)偏移 12-15: padding (4 字节填充为了让 v 对齐到 8 字节边界)偏移 16-23: v (8 字节)c 的偏移是 0i 的偏移是 4不是 1v 的偏移是 16不是 9 或 12sizeof(struct S3) 是 24union U3的偏移量和大小union的所有成员共享同一块内存起始地址相同。p-cp-i[0]p-v都从union的起始地址开始访问。union的大小取决于最大成员的大小并且满足最大对齐要求。union可以节省空间。二叉树例子中structnode_s{structnode_s*left;structnode_s*right;doubledata[2];};每个节点都是32字节两个指针8816double data[2]16。但是叶子节点不需要left/right内部节点不需要data所以有一半空间浪费。改成unionunionnode_u{struct{unionnode_u*left;unionnode_u*right;}internal;doubledata[2];};内部节点用 internal.left、internal.right叶子节点用 data[0]、data[1]。因为 internal 和 data[2] 互斥使用所以只需要 16 字节而不是 32 字节。可以通过引入一个枚举类型并创建结构体来判断节点是叶子节点还是内部节点。typedefenum{N_LEAF,N_INTERNAL}nodetype_t;structnode_t{nodetype_ttype;union{struct{structnode_t*left;structnode_t*right;}internal;doubledata[2];}info;};type 占 4 字节type 后面通常有 4 字节填充使 info 按 8 字节对齐info 占 16 字节union读取double的位模式unsignedlongdouble2bits(doubled){union{doubled;unsignedlongu;}temp;temp.dd;returntemp.u;}这里不是把 double 的数值转成整数而是把同一块内存按另一种类型重新解释。doubled3.14;unsignedlongudouble2bits(d);u 里保存的是 d 的 IEEE 754 位模式包括符号位、指数和尾数。u 的数值通常和 d 的数值没有直接关系除非 d 0.0 这种特殊情况。数据对齐为什么要数据对齐处理器和内存之间的接口如果要求数据对齐设计会更简单。假设处理器一次从内存读取 8个字节。如果一个 double8字节的地址是 8的倍数对齐了处理器只需要 1次 内存操作就能读完。如果地址没对齐比如地址是3这个 double 就会跨越两个8字节的内存块。处理器就需要执行 2次 内存访问再把数据拼起来效率就低了。对齐的基本原则K 字节的基本对象其地址必须是 K 的倍数。类型大小 (字节)对齐要求 (K)地址必须是…的倍数char111 (任意地址)short222int,float444long,double,char*888编译器的工作编译器会在汇编代码中插入指令如 .align 8确保全局数据的起始地址满足对齐要求。结构体Struct中的对齐陷阱编译器为了保证结构体里的每个成员都满足对齐要求会做两件事插入间隙Padding 和 结构体整体对齐。情况一内部填充structS1{inti;charc;intj;};如果不填充紧凑排列i 在偏移 0-3满足4字节对齐。c 在偏移 4满足1字节对齐。j 在偏移 5-8。但是j 是 int需要4字节对齐但地址 5 不是 4 的倍数。编译器的做法插入间隙i 在偏移 0-3。c 在偏移 4。插入 3 个字节的空隙偏移 5, 6, 7 浪费掉。j 从偏移 8 开始。 8 是 4 的倍数。虽然数据只有 9 字节414但结构体大小变成了 12 字节情况二结构体末尾的填充尾部填充structS2{inti;intj;charc;};成员分析i (0-3), j (4-7), c (8)。看起来似乎只要 9 字节就够了但是需要填充到12字节。考虑如果定义了一个数组struct S2 d[4];如果每个结构体只占 9 字节d[0] 起始地址是 X。d[1] 起始地址是 X 9。d[1] 里面的第一个成员 i 的地址就是 X 9。如果 X 是 4 的倍数那么 X 9 绝对不是 4 的倍数。这就导致 d[1] 里的 i 没有对齐编译器的做法强行把结构体 S2 的大小补齐到 12 字节最后补 3 个字节空隙。这样 d[1] 的地址就是 X 12。因为 12 是 4 的倍数所以 d[1] 里的 i 依然能保持对齐。