In this part we will look into a special memory region of the process called the Stack. This chapter covers Stack’s purpose and operations related to it. Additionally, we will go through the implementation, types and differences of functions in ARM.

本节我们将关注一块叫栈的特殊的内存区域。本章介绍了堆栈的作用和与之相关的操作。此外，我们将介绍ARM函数如何实施，函数类型及其差异。

Generally speaking, the Stack is a memory region within the program/process. This part of the memory gets allocated when a process is created. We use Stack for storing temporary data such as local variables of some function, environment variables which helps us to transition between the functions, etc. We interact with the stack using PUSH and POP instructions. As explained in Part 4: Memory Instructions: Load And Store，PUSH and POP are aliases to some other memory related instructions rather than real instructions, but we use PUSH and POP for simplicity reasons.

一般来说，堆栈是程序/进程内的一块内存区域。创建进程后，会开辟出这样一块内存空间。我们使用堆栈来存储临时数据，例如一些函数的局部变量、环境变量，这些变量可以帮助我们在函数之间转换，等等。我们使用push，pop指令来和栈交互，正如第4部分《载入和存储》中所解释的：PUSH和POP是一系列其他的内存相关指令的总称的别名，而不是实际指令，但为了让事情变得简单，我们使用了PUSH和POP。 

Before we look into a practical example it is import for us to know that the Stack can be implemented in various ways. First, when we say that Stack grows, we mean that an item (32 bits of data) is put on to the Stack. The stack can grow UP(when the stack is implemented in a Descending fashion) or DOWN (when the stack is implemented in a Ascending fashion). The actual location where the next (32 bit) piece of information will be put is defined by the Stack Pointer, or to be precise, the memory address stored in the SP register. Here again, the address could be pointing to the current (last) item in the stack or the next available memory slot for the item. If the SP is currently pointing to the last item in the stack (Full stack implementation) the SP will be decreased (in case of Descending Stack) or increased (in case of Ascending Stack) and only then the item will placed in the Stack. If the SP is currently pointing to the next empty slot in the Stack, the data will be first placed and only then the SP will be decreased (Descending Stack) or increased (Ascending Stack).

在看一个实际的例子之前，我们应该知道，堆栈可以用不同的方式来实现。首先，当我们说堆栈生长了，意思是一个项目（32位长度的数据）被压入堆栈了。堆栈可以长大（以堆栈地址降低方式实现）或减小（以堆栈地址升高方式实现）。下个项目（32位）信息将被放置的实际地址由堆栈指针定义，或者确切地说，这个地址是被存储在SP寄存器中的。地址可能会指向堆栈中当前（最新）的项目，或指向当前项的下一项的可用的内存槽。如果SP当前指向堆栈中的最后一个项目（完整堆栈实现），SP将先减少（在堆栈降序排列的情况下）或增加（在栈升序排列的情况下），并且只有这么做后，项目才能被放置在堆栈中。如果SP当前指向栈中的下一个空白内存槽，则数据将首先被放置在这里，并且SP将被减少（降序堆栈）或增加（升序堆栈）。

以下总结了不同堆栈实现方式，我们可以使用下表来描述在不同情况下，存储多个指令和载入多个指令在不同情形下是如何使用的。

In our examples we will use the Full descending Stack. Let’s take a quick look into a simple exercise which deals with such a Stack and it’s Stack Pointer.

本例中我们使用全递减堆栈。让我们快速查看一个处理堆栈和堆栈指针的简单练习。

/* azeria@labs:~$ as stack.s -o stack.o && gcc stack.o -o stack && gdb stack */
.global main

main:
     mov   r0, #2  /* set up r0 设置R0的数值 */
     push  {r0}    /* save r0 onto the stack 将R0压入栈*/
     mov   r0, #3  /* overwrite r0 覆盖R0*/
     pop   {r0}    /* restore r0 to it's initial state 将R0恢复到初始状态*/
     bx    lr      /* finish the program 程序结束*/

At the beginning, the Stack Pointer points to address 0xbefff6f8 (could be different in your case), which represents the last item in the Stack. At this moment, we see that it stores some value (again, the value can be different in your case):

一开始堆栈指针指向地址0xBEFFF6F8（可能与您的地址不同），它表示堆栈中的最后一个项。此时，我们看到它存储了一些数值（同样，在您的情况下，值可以不同）：

gef> x/1x $sp
0xbefff6f8: 0xb6fc7000

在执行第一个指令 （MOV）之后，堆栈方面没有任何改变。当执行完PUSH指令时，发生以下情况：首先，SP的值减少了4（4字节＝32位）。然后，R0的内容被存储到由SP指定的新地址中。当我们现在检查SP所引用的更新过的内存地址时，我们看到在该地址存储了32位的整数2：

gef> x/x $sp
0xbefff6f4: 0x00000002

The instruction (MOV r0, #3) in our example is used to simulate the corruption of the R0. We then use POP to restore a previously saved value of R0. So when the POP gets executed, the following happens: first, 32 bits of data are read from the memory location (0xbefff6f4) currently pointed by the address in SP. Then, the SP register’s value is increased by 4 (becomes 0xbefff6f8 again). The register R0 contains integer value 2 as a result.

我示例中的指令（MOV R0，#3）用于模拟R0被损坏了。然后，我们使用POP恢复先前保存的R0值。因此，当POP被执行时，发生以下情况：首先，从SP中当前地址指向的内存位置（0xBEFFF6F4）读取32位长度的数据。然后，SP寄存器的值增加4（再次成为0xBeffF6F8）。结果寄存器R0包含整数值2。

gef> info registers r0
r0       0x2          2

Please note that the following gif shows the stack having the lower addresses at the top and the higher addresses at the bottom, rather than the other way around like in the first illustration of different Stack variations. The reason for this is to make it look like the Stack view you see in GDB)

请注意，下面的GIF显示堆栈的顶部地址较低，底部的地址较高（译者注：之前是相反的）。此时堆栈变化了，已经不同于第一个图片里的那种形式。这样做的原因是使它看起来更像在GDB中看到的堆栈视图。

We will see that functions take advantage of Stack for saving local variables, preserving register state, etc. To keep everything organized, functions use Stack Frames, a localized memory portion within the stack which is dedicated for a specific function. A stack frame gets created in the prologue (more about this in the next section) of a function. The Frame Pointer (FP) is set to the bottom of the stack frame and then stack buffer for the Stack Frame is allocated. The stack frame (starting from it’s bottom) generally contains the return address (previous LR), previous Frame Pointer, any registers that need to be preserved, function parameters (in case the function accepts more than 4), local variables, etc. While the actual contents of the Stack Frame may vary, the ones outlined before are the most common. Finally, the Stack Frame gets destroyed during the epilogue of a function.

我们看到，函数利用堆栈来保存局部变量，保存寄存器状态等。为了让所有事物有序运行，函数使用栈帧，即堆栈中的一片本地化内存区域，专用于特定的函数。栈帧是在函数的prologue（下一节中有更多内容）中创建的。将帧指针（FP）设置到堆栈帧的底部，然后为栈帧分配的堆栈缓存会被开辟。栈帧（从它的底部开始）通常包含返回地址（之前的LR）、之前的帧指针、需要保存的任何寄存器、函数参数（如果函数允许大于4）、局部变量等。虽然堆栈帧的实际存储的内容可能有所不同，但之前概述的那些内容是最常见的。最后，堆栈帧在函数运行到结尾部分时被破坏。

Here is an abstract illustration of a Stack Frame within the stack: 下图是栈中栈帧的抽象简图

As a quick example of a Stack Frame visualization, let’s use this piece of code: 作为堆栈框架可视化的一个快速示例，让我们使用这段代码：

/* azeria@labs:~$ gcc func.c -o func && gdb func */
int main()
{
 int res = 0;
 int a = 1;
 int b = 2;
 res = max(a, b);
 return res;
}

int max(int a,int b)
{
 do_nothing();
 if(a<b)
 {
 return b;
 }
 else
 {
 return a;
 }
}
int do_nothing()
{
 return 0;
}

In the screenshot below we can see a simple illustration of a Stack Frame through the perspective of GDB debugger. 在下面的截图中，我们可以通过GDB调试器来简单地观察栈帧。

We can see in the picture above that currently we are about to leave the function max (see the arrow in the disassembly at the bottom). At this state, the FP (R11) points to 0xbefff254 which is the bottom of our Stack Frame. This address on the Stack (green addresses) stores 0x00010418 which is the return address (previous LR). 4 bytes above this (at 0xbefff250) we have a value 0xbefff26c, which is the address of a previous Frame Pointer. The 0x1 and 0x2 at addresses 0xbefff24c and 0xbefff248 are local variables which were used during the execution of the function max. So the Stack Frame which we just analyzed had only LR, FP and two local variables.

我们可以在上面的图片中看到当前我们将要离开函数max（见图中底部的箭头）。在这种状态下，FP（R11）指向0xBEFFF254，这里是栈帧的底部。堆栈上的地址（绿色地址）存储0x000 010418，这是返回地址（之前的LR）。 0xBEFFF254 上面的4字节（0xBEFFF250）中存储了值0xBEFFF26C，它是上一个的帧指针的地址。地址0xBEFFF24C处的 0x1和0xBEFFF248处0x2是函数max执行过程中用到的局部变量。因此，对于刚才栈帧，我们只分析了其中的LR、FP，以及两个局部变量。

To understand functions in ARM we first need to get familiar with the structural parts of a function, which are:

想理解ARM函数首先需要熟悉函数的结构组成，他们是：

The purpose of the prologue is to save the previous state of the program (by storing values of LR and R11 onto the Stack) and set up the Stack for the local variables of the function. While the implementation of the prologue may differ depending on a compiler that was used, generally this is done by using PUSH/ADD/SUB instructions. An example of a prologue would look like this:

prologue（序言）的目的是保存程序的先前状态（通过将LR和R11的值存储到堆栈上）并为函数的局部变量开辟堆栈空间。虽然序言的实现可能取决于所使用的编译器，但通常通过使用PUSH/ADD/SUB指令来完成。有这样一个例子：

push   {r11, lr}    /* Start of the prologue. Saving Frame Pointer and LR onto the stack序言开始，保存FP并将LR入栈 */
add    r11, sp, #0  /* Setting up the bottom of the stack frame 设置栈帧的底部*/
sub    sp, sp, #16  /* End of the prologue. Allocating some buffer on the stack. This also allocates space for the Stack Frame 序言的终止，在栈上分配一些缓存区，这样也为栈帧分配了一些内存空间*/

The body part of the function is usually responsible for some kind of unique and specific task. This part of the function may contain various instructions, branches (jumps) to other functions, etc. An example of a body section of a function can be as simple as the following few instructions:

函数的主体部分通常负责执行某种特殊的和特定的任务。函数的这一部分可以包含多种指令、分支（跳转）到其他函数等。函数的函数主体部分的示例可以与以下几个指令一样简单：

mov    r0, #1       /* setting up local variables (a=1). This also serves as setting up the first parameter for the function max */
mov    r1, #2       /* setting up local variables (b=2). This also serves as setting up the second parameter for the function max */
bl     max          /* Calling/branching to function max */

The sample code above shows a snippet of a function which sets up local variables and then branches to another function. This piece of code also shows us that the parameters of a function (in this case function max) are passed via registers. In some cases, when there are more than 4 parameters to be passed, we would additionally use the Stack to store the remaining parameters. It is also worth mentioning, that a result of a function is returned via the register R0. So what ever the result of a function (max) turns out to be, we should be able to pick it up from the register R0 right after the return from the function. One more thing to point out is that in certain situations the result might be 64 bits in length (exceeds the size of a 32bit register). In that case we can use R0 combined with R1 to return a 64 bit result.

上面的示例代码显示了一个函数的片段，它设置局部变量，然后分支到另一个函数。这段代码还告诉我们，函数的参数（在这种情况下是函数max的参数）如何通过寄存器传递。在某些情况下，当有超过4个参数需要被传递时，我们将使用堆栈来存储剩余的参数。还值得一提的是，函数的结果是通过寄存器R0返回的。因此，无论函数（max）的结果究竟是什么，我们应该能够在函数返回之后，从寄存器R0中把它提取出来。还有一点要指出的是，在某些特定情况下，返回值的长度可能是64位的长度（超过32位寄存器的大小）。在这种情况下，我们可以使用R0与R1组合起来，来返回64位结果。

The last part of the function, the epilogue, is used to restore the program’s state to it’s initial one (before the function call) so that it can continue from where it left of. For that we need to read just the Stack Pointer. This is done by using the Frame Pointer register (R11) as a reference and performing add or sub operation. Once we readjust the Stack Pointer, we restore the previously (in prologue) saved register values by poping them from the Stack into respective registers. Depending on the function type, the POP instruction might be the final instruction of the epilogue. However, it might be that after restoring the register values we use BX instruction for leaving the function. An example of an epilogue looks like this:

函数的最后一部分，尾声（epilogue），用来将程序恢复到初始状态（调用函数之前的状态），所以可以接着从函数被调用之前的位置继续往后执行。为了实现该目标，我们需要读取堆栈指针（SP）。这是通过使用帧指针寄存器（R11）作为参考并执行加法或者减法操作来完成的。当我们重新调整堆栈指针时，我们通过将它们从堆栈中弹出到各自的寄存器中来恢复先前（序言）保存的寄存器值。POP指令可能是结尾部分的最后指令，这取决于函数的类型 。但是，在恢复寄存器值之后，我们可能会使用BX指令来离开函数。尾声（Epilogue）的一个例子是这样的：

sub    sp, r11, #0  /* Start of the epilogue. Readjusting the Stack Pointer 尾声开始，调整SP寄存器*/
pop    {r11, pc}    /* End of the epilogue. Restoring Frame Pointer from the Stack, jumping to previously saved LR via direct load into PC. The Stack Frame of a function is finally destroyed at this step. 尾声的结束。从堆栈中恢复之前的FP，并把之前保存的LR载入PC，跳转到那里继续执行。函数的栈帧至此全部销毁完毕*/

So now we know, that:所以我们知道了：

Prologue sets up the environment for the function; 序言部分建立了函数的运行环境

Body implements the function’s logic and stores result to R0;函数体部分实现函数的逻辑并将返回值存储进R0

Epilogue restores the state so that the program can resume from where it left of before calling the function.尾声部分恢复了函数被调用之前的状态并继续运行。

Another key point to know about the functions is their types:leaf and non-leaf. The leaf function is a kind of a function which does not call/branch to another function from itself. A non-leaf function is a kind of a function which in addition to it’s own logic’s does call/branch to another function. The implementation of these two kind of functions are similar. However, they have some differences. To analyze the differences of these functions we will use the following piece of code:

了解函数的另一个关键点是它们的类型：叶和非叶。叶函数是这样一类函数，它本身不调用/分支另一函数。非叶函数是一种函数，除了它自己的逻辑外，还得调用/分支到另一个函数。这两种函数的实现是相似的。然而，它们有一些不同之处。为了分析这些函数的差异，我们将使用下面的代码：

/* azeria@labs:~$ as func.s -o func.o && gcc func.o -o func && gdb func */
.global main

main:
	push   {r11, lr}    /* Start of the prologue. Saving Frame Pointer and LR onto the stack序言开始，保存FP，LR入栈 */
	add    r11, sp, #0  /* Setting up the bottom of the stack frame设置栈帧的底部 */
	sub    sp, sp, #16  /* End of the prologue. Allocating some buffer on the stack 序言结束，分配一些栈缓存区域*/
	mov    r0, #1       /* setting up local variables (a=1). This also serves as setting up the first parameter for the max function 设置局部变量（a=1),这也为max函数设置了第一个参数*/
	mov    r1, #2       /* setting up local variables (b=2). This also serves as setting up the second parameter for the max function 设置局部变量(b=2),这为max函数设置了第二个变量*/
	bl     max          /* Calling/branching to function max 分支/跳转到函数max*/
	sub    sp, r11, #0  /* Start of the epilogue. Readjusting the Stack Pointer 尾声部分开始，重新调整堆栈指针SP*/
	pop    {r11, pc}    /* End of the epilogue. Restoring Frame pointer from the stack, jumping to previously saved LR via direct load into PC 尾声的结束，将FP指针从堆栈中恢复，通过将之前的LR装载进PC中，实现了跳转到之前的位置继续执行*/

max:
	push   {r11}        /* Start of the prologue. Saving Frame Pointer onto the stack 序言开始，FP入栈*/
	add    r11, sp, #0  /* Setting up the bottom of the stack frame 设置栈帧的底部*/
	sub    sp, sp, #12  /* End of the prologue. Allocating some buffer on the stack 序言结束。分配栈空间*/
	cmp    r0, r1       /* Implementation of if(a<b) 实施if(a<b)指令*/
	movlt  r0, r1       /* if r0 was lower than r1, store r1 into r0 如果r0小于r1就将r1存入r0*/
	add    sp, r11, #0  /* Start of the epilogue. Readjusting the Stack Pointer 尾声的开始，重新调整SP*/
	pop    {r11}        /* restoring frame pointer 恢复FP*/
	bx     lr           /* End of the epilogue. Jumping back to main via LR register 尾声阶段结束，通过LR跳转回主函数*/

The example above contains two functions: main, which is a non-leaf function, and max – a leaf function. As mentioned before, the non-leaf function calls/branches to another function, which is true in our case, because we branch to a function max from the function main. The function max in this case does not branch to another function within it’s body part, which makes it a leaf function.

上面的例子包含了两个函数，main函数是非叶函数而max是叶函数。正如之前所提到的，非叶函调用/分支到其他函数，本例就是这样的，因为我们从在main函数里分支到max函数了。但本例中的max函数并没有在他的函数内部分支到其他函数，这使他成为了叶函数

Another key difference is the way the prologues and epilogues are implemented. The following example shows a comparison of prologues of a non-leaf and leaf functions另一个很关键的差异是:序言和尾声的实现方式不同。下面的例子比较了叶函数和非叶函数的序言

/* A prologue of a non-leaf function */
push   {r11, lr}    /* Start of the prologue. Saving Frame Pointer and LR onto the stack */
add    r11, sp, #0  /* Setting up the bottom of the stack frame */
sub    sp, sp, #16  /* End of the prologue. Allocating some buffer on the stack */

/* A prologue of a leaf function */
push   {r11}        /* Start of the prologue. Saving Frame Pointer onto the stack */
add    r11, sp, #0  /* Setting up the bottom of the stack frame */
sub    sp, sp, #12  /* End of the prologue. Allocating some buffer on the stack */

The main difference here is that the entry of the prologue in the non-leaf function saves more register’s onto the stack. The reason behind this is that by the nature of the non-leaf function, the LR gets modified during the execution of such a function and therefore the value of this register needs to be preserved so that it can be restored later. Generally, the prologue could save even more registers if it’s necessary.

主要的不同在于，非叶函数的序言需要将更多的寄存器保存在堆栈里。背后的原因在于，由于非叶函数的天然属性，在执行这样的函数期间LR被修改了，因此需要保存该寄存器的值，以便以后能够恢复。一般来说，如果必要的话，序言可以保存更多的寄存器。

The comparison of the epilogues of the leaf and non-leaf functions, which we see below, shows us that the program’s flow is controlled in different ways: by branching to an address stored in the LR register in the leaf function’s case and by direct POP to PC register in the non-leaf function.

下面我们看看叶和非叶函数的尾声的比较，下面展示了程序的流以不同的方式控制：遇到叶函数的情况下就分支到存储在LR寄存器中的地址，而遇到非叶函数时直接POP地址到的PC寄存器。

 /* An epilogue of a leaf function */
add    sp, r11, #0  /* Start of the epilogue. Readjusting the Stack Pointer */
pop    {r11}        /* restoring frame pointer */
bx     lr           /* End of the epilogue. Jumping back to main via LR register */

/* An epilogue of a non-leaf function */
sub    sp, r11, #0  /* Start of the epilogue. Readjusting the Stack Pointer */
pop    {r11, pc}    /* End of the epilogue. Restoring Frame pointer from the stack, jumping to previously saved LR via direct load into PC */

Finally, it is important to understand the use of BL and BX instructions here. In our example, we branched to a leaf function by using a BL instruction. We use the the label of a function as a parameter to initiate branching. During the compilation process, the label gets replaced with a memory address. Before jumping to that location, the address of the next instruction is saved (linked) to the LR register so that we can return back to where we left off when the function max is finished.

最后，重要的是理解BL和BX指令在这里的使用。在我们的例子中，我们使用BL指令分支到叶函数。我们使用函数的标签作为参数来启动分支。在编译过程中，标签被替换为内存地址。在跳转到该位置之前，下一条指令的地址被保存（链接）到LR寄存器，这样我们就可以返回到函数max结束时离开的位置。

The BX instruction, which is used to leave the leaf function, takes LR register as a parameter. As mentioned earlier, before jumping to function max the BL instruction saved the address of the next instruction of the function main into the LR register. Due to the fact that the leaf function is not supposed to change the value of the LR register during it’s execution, this register can be now used to return to the parent (main) function. As explained in the previous chapter, the BX instruction  can exchange between the ARM/Thumb modes during branching operation. In this case, it is done by inspecting the last bit of the LR register: if the bit is set to 1, the CPU will change (or keep) the mode to thumb, if it’s set to 0, the mode will be changed (or kept) to ARM. This is a nice design feature which allows to call functions from different modes.

用于离开叶函数的BX指令以LR寄存器作为参数。如前所述，在跳转到函数max之前，BL指令将函数main的下一个指令的地址保存到LR寄存器中。由于叶函数不在执行期间改变LR寄存器的值，所以该寄存器现在可以用于返回父（main）函数。如前一章所解释的，BX指令可以在分支操作期间在ARM/Thumb模式之间进行交换。在这种情况下，它是通过检查LR寄存器的最后一位来完成的：如果位被设置为1，CPU将模式切换（或保持）为Thumb，如果设置为0，则模式将被改变（或保持）为ARM模式。这是一个很好的设计特性，允许从不同模式来调用函数。

To take another perspective into functions and their internals we can examine the following animation which illustrates the inner workings of non-leaf and leaf functions.

为了从另一个角度观察函数及其内部结构，我们可以看看下面的动画，它说明了非叶和叶函数的内部工作状况。