第七章运行时存储空间组织

type

status

date

slug

summary

运行时存储空间的组织

运行时环境就是程序运行时的一些环境

一些概念：

函数（所指的就是函数中的函数）的活动：

函数活动的时候需要的信息如下：

需要源代码及信息的数据结构

活动记录：就是函数活动所需的可执行代码还有存放信息的数据结构（也就是函数活动需要的信息）

关于活动记录就需要考虑活动记录的数据安排（单个活动记录的结构）和组织方式（多个活动记录的串联）

活动记录（动态链）

活动记录通常使用栈来存储（想想中间代码生成那边的栈帧），所以在栈模式下函数返回就意味着栈帧出栈，这个时候函数的栈帧（活动记录）也就不再被栈维护，也就是不再被引用了

但是如果使用的不是栈模式的话就有可能继续引用，例如下面的js代码（js是动态语言，是将函数的栈帧分配在堆上的，也就是堆模式）：

上面实际上就是一个js函数闭包。这里Create函数的活动记录中存储着counter的值，但是由于闭包的调用，这里调用create函数返回之后并没有消除counter的活动记录（counter仍然在函数外部在引用），也就是js通过函数闭包实现了活动记录的保留（延长了变量的声明周期）

这个时候counter在f（）内还是可以访问的，所以就可以发现，变量能不能访问是要看作用域上层的，而不是看当前函数的调用者

下面这张图中的实线表示函数的调用关系，而虚线则是变量查找的关系（f（）中如果没有变量counter就从Create中找，也就是上面一段总结的）

上面的实线实际上就是这里所说的动态链，也就是函数调用关系（这个链接不是固定的，所以叫做动态链）

上面的虚线就是下面说的静态链，指向的是当前函数内调用了，但是没有定义在当前函数内的变量（也就是非局部变量，如上面的虚线）。所以当当前函数中调用了变量，但是在当前函数中没有找到变量的声明的话，就要沿着静态链向上寻找。由于变量的向上查找是固定的，所以叫做静态链（就比如上面的f（）函数，就不会跑到MyFunc里面去找这个counter）

如下图，看下面这个标题就知道之前的栈帧就是现在所说的活动记录

函数的调用和返回需要使用栈（也就是需要使用栈式存储，四轴的汇编中转子程序push的时候其实有讲将LR寄存器中的值存入堆栈，这里就是函数的栈式存储），而不能使用跳转指令（因为没有办法找到返回地址了），也不能使用寄存器（因为寄存器数量有限，如果函数深度够深的话寄存器也不够用）

也就是需要使用下图所说的模式（想想计组里面的转子命令的执行过程和返回指令的执行过程）：

就是计组里面的一些指令

转子指令会将当前的地址压入堆栈（保存返回地址），而返回指令就会去堆栈中取出返回地址

这里的rip应该就是上一个函数（也就是当前函数的主调函数）的指令地址（因为函数返回的时候需要返回之前的指令，这里保存的其实也就是当前指令的下一条指令的地址），所以我们能发现函数的指令返回地址的保存是在使用call指令的时候的

在子函数中（被调函数）是没办法主动去获取参数的，因为参数是在主调函数中定义的，想想c语言的函数，实现函数的时候都只是提供一个参数的类型，子函数是不知道传入的参数是什么样的，所以参数的传递需要在主调函数中完成（但是写汇编的时候就不一样，因为变量在哪个寄存器中是由我们自己决定的，这些参数对所有的proc都是可见的），也就是下图：

这里可以发现是先将函数的参数逆序压栈，然后再压入主调函数的指令地址。

这里压入指令地址之后就是将之前的函数的栈帧地址压栈（右边是汇编代码，所以rbp指向的是上一个函数的栈帧）。注意这里的rsp是栈顶指针

存入主调函数的栈帧指针的时候先将栈顶指针移动到栈顶（由计算机自己完成），然后需要记录当前函数的栈帧地址，也就是当前的栈顶指针的值（所以在中间代码生成那边提到的，函数的栈帧指针的位置是在压入的参数和主调函数的栈帧之间。这里由一点点小小的出入，之前是先压入主调函数的栈帧指针，然后再压入返回地址，这里是反过来的，先压入返回地址，然后再压入栈帧指针）

接下来就是函数的局部变量还有临时变量了

关于函数调用时红区的一点说明——红区就是一种优化，如下图

函数调用小结（这个屁用没有）：

活动记录存储的内容

从上面可以发现活动记录存储的内容有

当前函数的主调函数传入的参数（逆序压栈），也就是形式参数

主调函数的返回地址，是cpu现场的一种

主调函数的栈帧指针，是cpu现场的一种

当前函数的局部变量和临时变量（之前中间代码生成的时候提到的）

更具体地，活动记录存储的内容如下图：

现在就有一个问题，需要为一个函数分配多大的栈帧（这个就是由函数的局部变量和临时变量决定的了）

对于变量类型可以在编译时确定的语言（也就是静态语言），他们的栈帧大小就可以在编译时通过数据类型来确定，之后如果出现该函数的调用的话就直接创建对应大小的栈帧（也就是将栈顶指针直接向下移动若干个单位），并且根据这些变量声明的顺序进行栈帧的内存分配，这样就可以在栈帧中对局部变量进行随机访问了（也就是下图中最后说的局部数据的首地址）

接下来就是什么语言能够在编译时确定这些信息的问题了

语言的类型

静态变量：当前变量的函数的活动记录位置（与函数的栈帧指针有关）和当前变量的大小（与当前变量的类型有关）都能确定下来，如下图：

由于静态语言每一个函数的栈帧位置在编译的时候就确定了，所以是没有办法进行递归的（因为递归的时候需要同一个函数有不同的栈帧，但是在静态语言中，只要是同一个函数，栈帧就是一样的）

并且变量的大小确定就没办法使用动态数组了（因为动态数组的大小是没办法确定的）

半静态变量：当前活动记录的位置（也就是栈帧指针的位置）在运行时能确定下来，并且变量的大小能够在编译时确定下来。如下图：

这个时候函数就能够进行递归调用了（因为同一函数用的不是一个栈帧），但是还是没办法支持动态数组（因为栈帧的大小在编译时就确定了），半静态语言的一个典型例子就是c语言

半动态语言：当前函数的栈帧指针和变量的大小都没办法在编译时确定，但是在运行时都能确定下来，如下图：

这个时候函数可以递归（因为栈帧不是唯一的，可以栈式分配），并且可以使用动态数组（因为当前变量的大小是运行时决定的，说通俗一点就是能够在程序运行的时候确定下来，比如c99输入一个变量然后用这个变量开一个数组），典型语言就是c99

此时还是需要在运行时确定下来栈帧的大小，所以在编译的时候虽然没办法确定，但是需要一些标识符字段便于在运行时分配变量空间，也就是下图：

所以在编译的时候为这些半动态变量存储的是标识符信息，然后运行时根据实际运行情况以及编译时记录的标识符来开栈帧的大小

由于半动态变量需要在运行的时候分配栈空间，所以只能分配在当前栈帧的栈顶（因为如果不在栈顶的话就会把其他的变量挤掉）也就是下图：

动态语言：当前函数的栈帧指针和当前变量的大小在编译运行时都没办法确定，如下图：

此时就不能进行栈式分配了，因为运行某一个函数的时候栈底下的变量空间需要扩充

这个时候就只能使用堆式分配，将动态变量分配在堆上，这样如果要改变变量的空间，就可以将原有的变量free掉，然后重新分配空间。由于是分配在堆上，只有自己free掉了或者被gc回收的时候才会消失，而不会像栈式分配那样随着函数的返回而消失

所以计算机内的堆栈是这样的：

是一个类似双端栈一样的东西，所以这里的静态变量还有动态变量都是分配在上端的

考试的重点是栈式分配，所以这里只考虑半动态语言还有半静态语言

半静态语言的栈式分配

主要考察函数调用和返回时的操作

这个就是一个具体的分配的例子了，跟上面是吻合的（这里的current就是栈帧地址），调用函数的时候就先压入函数的参数，然后压入主调函数的返回地址，然后再存入主调函数的栈帧地址（也就是动态链接），然后根据当前的栈顶指针创建当前函数的栈帧指针，然后因为是半静态变量，此时栈帧的大小就是确定的，此时就可以直接移动栈顶指针（这里的free）来进行栈帧大小的分配

方括号代表取值（跟计组的圆括号不一样）

栈帧的保存就是一个动态链接（因为当前函数的栈帧是在主调函数的栈帧之上的）

再来理一遍函数调用的全过程：

首先先将函数的参数压栈（主调函数实现，也就是在call指令之前，应该是算在主调函数的活动记录内的），然后通过call指令保存下一条指令的地址（也进入就是上图的部分）。接下来就是保存动态链（也就是保存主调函数的栈帧），然后就是更新动态链节点（也就是将free的值赋给current，这个时候current就指向了返回地址单元。注意这个free并不是实际上的栈顶指针，而是一个用来跟踪栈帧栈顶的指针），然后根据预先计算好的栈帧大小开辟栈空间（就是上图中的L），最后进行跳转（至此call命令结束）

这里的问号处应该填写ip+4，也就是下一条指令（这个指令指的是汇编的指令，而标题中的call指令应该是ir中的call指令）的下四条指令。也就是执行第一行的时候，ip就是第二行，ip+4就是第6行了

这里是IP+x是因为call指令之后可能还有一些返回时无用的指令（如保存栈帧等等），所以需要加上x

注意这里的free和current表示的是栈帧的栈顶和栈底（所以free是自己创建的指针，而current就是栈帧指针rbp）

函数的返回如下（活动记录的返回）：

需要先将栈帧空间释放（也就是free=current）

然后需要返回活动记录（一定要在指令返回之前，一方面是因为栈的出栈顺序，另一方面就是返回了之后如果还没有恢复主调函数的活动记录可能导致指令会取到被调函数的活动记录中的值。也就是上图中的current=D[current+1]，为什么是+1？因为上面存储的时候current存储的是栈帧栈底的位置，也就是返回地址的地址，所以这个时候）

最后返回指令（ip=D[free]，这个时候里面就不能是current了，因为current已经改变了）

也就是下面的过程

半动态变量的栈式分配

由于半动态变量的函数栈帧的地址以及变量的空间是在编译的时候没办法确定的，只能在运行时确定，所以只能在编译的时候保存一些跟变量所需空间有关的信息，也就是——标识符（注意标识符中有一个指针域，用来指向变量分配的位置），如下图：

半动态变量的空间大小是可能变化的，所以只能分配在活动记录的栈顶（防止在下面把一些半静态变量顶没了）

所以半动态变量的分配如下：

首先在编译的时候确定与变量空间有关的信息（如数组的位数，元素的数据类型等等）还有一个准备指向变量实际分配地址的指针域（也就是准备指向栈顶，因为半动态变量只能分配在栈帧的顶部）

在运行时确定下来变量的空间大小的时候，在栈顶给动态变量分配实际的存储空间（这个时候半动态变量的标识符内的指针指向的就是当前分配空间的底部了），然后在这个时候修改变量中的指针域（也就是修改为当前的free指针的值）

最后将栈帧栈顶指针free上移至栈帧的栈顶（这个时候变量的标识符连上了他实际的存储空间）

如果接下来还需要分配一个半动态变量的话过程也是完全一样的（只不过在运行时给新的半动态变量分配内存的时候，标识符中的指针域需要修改为新的栈顶指针）

作用域

静态作用域规则

也就是直接沿着作用域嵌套关系向上查找（c语言的规则）

这个嵌套的层次就是嵌套的深度，这里B在A内部，就说明b的嵌套深度比a多1

上面这个题直接带入c语言的环境来看就好了

所以在fg中可以调用b但是没办法调用c

总结（如何根据嵌套层次图确定能否调用，以上图中的f为例）：

首先找到从根节点到f的路径，也就是aef，所以f可以直接调用这些作用域内的变量（变量也可以是函数）

所有上面找到的路径上节点的直接子节点f都可以调用（直接子节点实际上就是上面找到的节点中的变量），所以上图中f可以调用的变量有f（也就是递归）、g、b、e。（a不做考虑，因为在c语言中最外层的作用域是文件，也就是全局，是没办法调用的，但是如果a是函数的话，上面的嵌套图就是不完整的了）

静态作用域规则选择将当前的嵌套关系也保存到活动记录中，通过静态链相连接。当出现非局部环境的引用的时候就沿着静态链向上查找其他函数的活动记录（所以并不一定一个函数在另一个函数中使用，当前函数就能调用主调函数中的参数，因为函数调用关系是动态链，但是非局部的变量引用需要查找的是静态链）

注意这里静态链存储的位置是在栈帧的第三个单元（第一个单元是返回地址，第二个单元是动态链接，也就是栈帧指针），并且静态链指向的也是上层函数的栈帧指针位置

静态链和动态链的区别如下：

所以静态链是记录函数的实现在哪里的，但是动态链是记录函数的使用是在哪里的

总结——静态链和动态链的绘制：

根据函数实现的嵌套关系绘制嵌套树（这就能解释js的那个闭包了，因为使用counter变量的时候就是沿着静态链找到了上面的函数Create）

根据函数调用关系（关注函数的使用位置）绘制动态链

根据嵌套树绘制函数的静态链

注意静态链和动态链都是指向一个函数的栈帧的占栈底（也就是函数返回地址的位置。这里就可以发现动态链和静态链存储的都是栈帧底的地址，也就是当前函数动态静态前驱的返回地址）

存储了静态链之后就可以访问非局部变量了

非局部变量的地址计算：

实际上就是根据嵌套层次一层层沿着静态链向上找

也就是a是b的第一个外层，就需要取一次值，所以如果a是b的第n个外层，那么就需要取值n次（可以通过函数递归实现，注意静态链的位置是当前栈帧底地址+2）

如果考到了这个递归函数的实现的话就自己模拟一下函数的行为看看是不是对的

按道理函数的静态链是在编译的时候就能确定的（所以相当于在编译的时候给函数加上了一个属性来表示嵌套关系），应该也就是ppt下面所说的：

应该是指编译器在处理程序单元调用的时候建立

然后静态链接的创建是根据当前的栈帧来实现的

根据栈帧建立静态链的具体实现如下（枚举当前函数调用的状态，就是当上一个栈帧是a并且下一个栈帧就是b的时候的程序结构，所以这里需要保证能调用，所以na-nb最小的情况就是-1，因为在a中查找函数b的时候没办法向下寻找）：

注意这里是a调用b，而不是a调用b单元中的某个变量，所以这个时候两个层次做差之后还需要加一才是下图中的d（也就是d=na-（nb-1），也即d=na-nb+1）

从上面的分析中就能得到下列的表达式，这样就可以根据上一个栈帧来建立当前栈帧的静态链了（这里f中的+1就是上面分析出来的加一，这个公式要记一下，就是要记住是f（d+1））

这个时候就需要在创建栈帧的时候加上一步创建静态链了（也就是在使用call命令的时候）

注意这些指令都是在主调函数中完成的（而且这里的call并不是汇编的命令，而是ir中的call命令，最后翻译成中间代码需要多加这么多指令）

当执行到第一行的时候，ip是在第二行，所以ip+5就是在第7行，所以这个时候需要存储的是ip+5

动态作用域规则

参数传递

按值传递

就是将实参的值拷贝给当前函数的形参，这个时候在函数内部改变形参外部实参不受影响，因为只是修改了实参的副本，也就是c语言里面的值传递。

按引用传递

这个时候传入的函数的就是实际参数的引用（也就是地址），也就是函数的实参的地址和形参地址是相同的，所以这个时候在函数内部改变形参，外部实参也会改变，这也就是c语言中的引用传递

按结果传递

这个时候并没有说传入参数的形式是什么样的。所以应该只是zeq为了讲明白传值得结果才说的，不会单独考这个

这个就是将函数计算出来的形参结果拷贝给实参。这个时候在程序层面上表现是一样的，都是传入一个实参，然后在函数内对其进行操作之后实参都改变了。但是他跟引用传递的一个重要的区别就是：引用传递实参和形参就是一样的，是再操作同一个空间。而按结果传递实参和形参操作的空间是不同的，只是处理结束之后将形参的值复制给实参了

传值得结果

根据这中传参的名字实际上就能得出来了，就是进入函数的时候将实参的值拷贝给形参（也就是传值，值传递），然后函数返回的时候再将形参的值拷贝给实参（得结果，也就是按结果传递）

按名传递

这个比较难理解，ppt上分成了两种情况：

简单变量（也就是函数参数传入a的时候）就是一个引用传递，这个时候如果去按照表达式传参去计算的话就是不一样的了，所以还是就直接当成引用传递

对于表达式（如传入a+b，假如对应的形参是c），这个时候就需要在每一次访问形参c的时候计算实参a+b的值，也就是最上面一行中说的重新评估

下面是一些参数传递的例题：

接下来是关于函数栈帧大小计算的一点补充：

上图跟之前的理解没有区别，函数调用都对应一个栈帧，并且正在执行的函数的栈帧是在栈的顶部。访问局部变量的时候是通过当前栈帧的指针（也就是上面所说的基址指针）还有变量的偏移来进行调用的。当出现非局部变量的引用如果是静态作用域规则就需要去沿着静态链向上寻找，动态作用域规则就是沿着动态链向上寻找

总体上来说还是跟c语言老师说的一样，就是结构体的大小是跟占用空间最大的变量有关系的

此时比较短的变量就会出现下面的情况（有一些空间是空闲出来的）：

这样牺牲空间实际上是为了便于从结构体中取值（这样处理之后就知道没过四个字节就是结构体中的下一个变量了，以上例为例，如果按照char来进行分配的话，就不好找到long和int的开头了）

根据上面的一张图，结构体分配的时候不是每一个变量的大小都直接取最长的那个，而是说当出现数据大小不同的时候需要改变（比如上图中的从char到int的时候需要进行数据四字节对齐，便于取下面的整形值。所以这个对齐就好像是取不同类型数据之前的一个操作一样）

再以上面的char long char int 为例，首先存储一个char类型变量，然后编译器发现下一个变量是四个字节的，这个时候就进行数据对齐，将char扩展成四个字节，然后存储一个long变量，发现下一个变量的类型不同，但是占用空间没有当前的变量大，所以就不用进行数据对齐了，然后存入一个char类型的变量，然后发现下一个变量又是四个字节的，比当前变量占用的空间大，这个时候就将char类型进行对齐扩展成四个字节的（这里是按字节编址）

注意结构体这种东西都是存储在函数的栈帧中的，所以如果问到栈帧的大小是需要考虑数据对齐的

这个习题下午做一下：