Mirror from my personal blog

Introduction

Chapter III of CS: APP mainly describes x86_64 assembly in details, which gives a dictionary-like introduction. Nevertheless, the reason why performing this chapter is to give a vivid adhere of chapter V. In this post, I just elaborate a small part introduced by a few of section, that is the runtime stack.Refers to section 3.7~3.10, Stack frame is a major part in procedure calling and manipulation. It stores variables, procedure return address, and any thing may be pushed in according to complier’s flavor.

Big picture

csapp_big.jpg

Stack frame is a memory structure holds procedure. The main function of it is similar to the figure delivered above:

• control transfer,
• data transfer,
• local variables storage.

Notes: Regarding the array and struct or union, however, they are just stored in memory, without being specified whether should be stored in stack or heap file.

Every function refers to a particular interval of stack. As figured in the picture above, stack stores arguments for the calling of next procedure, caller preserve variable in register and memory and return address of the caller, which note as the PC back point.

When we combine control and data together, it will be more complex than before. That is what we refer as variable stack frame, and another miscellaneous.

Control transfer

Control transfer of procedure refers to the function calling. Suppose that function P() wonna call function Q(), once you embody this process, the program should pass some arguments, transfer the PC of %rip to the function Q(), then it go through the instructions in Q(), at last go back to the origin address of %rip when meet ret, which means that return the funtion P().

In x86_64 instruction set, there are three control instructions:

The call instruction has a target indicating the address of the instruction where the called procedure starts. Its operand, which is the address, could be direct or indirect. Go back to figure 3.3 could get more details.

Suppose we have details of function below:

Q:
    0x400540    addq %rdi, %rdi
    0x400543    movq %rdi, %rax
    0x400546    ret
    
P:
    0x400560    movq $-1, %rdi
    0x400563    call Q
    0x400568    ret
-------Origin status before call-------
%rsp: 0x7fffffffe888 --> 0x0
%rip: 0x400560
---------------------------------------

-------After execute call--------------
%rsp: 0x7fffffffe880 --> 0x400568(The address of the next ins of call)
%rip: 0x400540 (The atart of Q)
---------------------------------------

------------After ret------------------
%rsp: 0x7fffffffe888 --> 0x0
%rip: 0x400568 (last ins of P)
---------------------------------------

In this simple case, once P call Q, P push its next instruction address as its return address to the stack, then %rip gets start address of Q. When meeting ret, %rip get that address from stack then add address of %rsp according to the size of the cell. It is easy, right?

Data transfer

When passing control to another procedure, we usually pass arguments to the callee one, so as to evaluate the data then get target result. As is mentioned before, we refer %rdi as the 1st argument, %rsi the second, and so on. It is a convention of how x86-64 pass arguments. Marked in details, as below:

The point here is, also combine the control transmission, the caller should push it’s variable stored in callee saved registers, set the argument registers into target arguments, after preparing for the function call, the PC go to the target procedure.

As an example:

proc:
    pushq %rbp
    movq %rsp, %rbp  # %rbp is a caller saved register
    add  %edi, %esi  # add %rdi to %rsi
    add  %rsi, %rdx  # ---
    add  %rdx, %rcx  # ---
    sub  %rcx, %r8   # ---
    movq %r8, %rax   # ---
    popq %rbp
    ret              # return
    
call_proc:
    sub   $16, %rsp
    movq  %edi,  8(%rsp)
    xorq  %edi,  %edi
    add   $0x8,  %edi
    movq  $0x10, %esi
    movq  %0x43(%rsp),   %rdx
    movq  $0x125 %rcx
    call proc
    movq  (%rsp), %edi
    addq  %edi,  %rax
    ret
    
# -------- stack result ---------
# |             |   orig %edi   | 8
# |          (unused)           | 0
# |        return address       | -
# |    orig rbp:     0x0        | callee - 8
# -------------------------------

Notes: the unused space is prepare for SIMD usage. On this stage, we can ignore it.

The caller saved register %rbp is pushed and set it as origin stack start position.

Local variable storage

There many example that variable are stored in registers, but at times that local variable should be load in memory. The common cases is:

• There are not enough registers to hold all of the local data
• The address operator ‘&’ is applied to local variable, and hense we must be able to generate an address for it
• Some of the local variables are arrays or structures so that it should be accessed as array or structure references.

As for example code, please refer Figure 3.32

In convention, the former variable should be pushed in the higher address of stack and the later ones could be set in the lower ones. Such as:

|_____________________|
|___x2____|____x1_____| 16
|_________x3__________| 8
|_______________|__x4_| 0

Alignment

Many computer systems place restrictions on the allowable addresses for primitive data types, requiring that the address for some objects must be a multiple of some value K. Such restrictions simplify the design of hardware forming the interface between the processor and the memory system. Also, address of stack frame do the same thing, so as to be refered in a correct way. As an example of Practice Problem 3.49,

+------------------------+
+    return address      +  8
+------------------------+
+    saved %rbp          +  0
+------------------------+
+       (Unused)         + -8
+------------------------+
+                        + e1
+------------------------+
+                        +
+            P           + 8n bytes
+                        +
+------------------------+
+                        + e2
+------------------------+

Every part of the stack frame should be a multiple of 8, so that e1+P+e2 should be a multiple of 16, hense we could embed a slot of memory which address is a multiple of 8.

Variable-Size Stack Frames

The variable-size stack frames means that the size of stack frame could not be determined at compile time. Further more, the variable, maybe array of struct, should be referenced by its address. Therefore, we should use a technique of managing such condition.

As Figure 3.43 :

long vframe(long n, long idx, long *q) {
    long i;
    long *p[n];
      p[0] = &i;
      for (i = 1; i < n; i++)
      p[i] = q;
      return *p[idx];
}

Portions of generated assembly code:

vframe:
    pushq    %rbp        # Set old %rbp
    movq    %rsp, %rbp    # Set frame pointer
    subq    $16, %rsp    # Allocate space for array p
    leaq    22(, %rdi, 8), %rax    # Make it to be a multiple of 16
    andq    $-16, %rax
    subq    %rax, %rsp    # Allocate space for array p
    leaq    7(%rsp), %rax
    shrq    $3, %rax
    leaq    0(, %rax, 8), %r8
    movq    %r8, %rcx
    
    # .....
    
.L3:
    movq    %rdx, (%rcx, %rax, 8)    # Set p[i] to q
    addq    $1, %rax                 # Increment i
    movq    %rax, -8(%rbp)            # Store on the stack
.L2:
    movq    -8(%rbp), %rax            # Retrieve i
    cmpq    %rdi, %rax
    jl        .L3
    
#    .....
    leave
    ret

Note the way to refer the array is that, it refer it by pointer register %rbp

At last of the program, it restore the original pointer to the %rsp, then pop %rbp to restore the caller’s frame.

movq  %rbp, %rsp    # Set stack pointer to beginning of frame
popq  %rbp          # Restore

This instruction combination has the effect of deallocating the entire stack frame.