Mechanisms in Procedure

이번에는 process에서 function call을 진행할 때의 mechanism을 설명드리고자 합니다. function call을 진행할 때 해당 function이 있는 address로 단순히 jump를 하게 되면 여러 문제가 발생합니다. 하나는 called function이 모두 진행된 후 return하려 할 때 어느 address로 jump해야 하는지 알 수 없다는 점입니다. 단순히 register에 저장할 수도 있겠지만 function을 recursive하게 여러 번 call하게 되면 return address가 overwrite되어 돌아가지 못할 수 있을 것입니다. 또 다른 문제로는 이전에 사용하던 variable이 register에 남아있는 경우 또한 overwrite되어 사라질 수 있다는 점입니다. 이러한 문제가 발생하지 않도록 function call은 다음과 같은 mechanism이 필요합니다.

1. Passing control
   • procedure code(function)를 시작하고 return point로 돌아오는 것을 control
2. Passing data
   • argument를 전달하고 value를 return
3. Memory management
   • prodecure를 수행하는 중에 memory allocate하고 return 시 deallocate

이와 같은 mechanism은 desiner의 choice에 따라 여러 형태로 나타날 수 있습니다. 이를 Application Binary Interface(ABI)라고 합니다.

Stack structure

C를 포함한 여러 programming language에서는 위와 같은 mechansim을 구현하기 위해 stack data structure를 사용합니다. function을 call하고 return하는 과정에서 가장 마지막에 call된 function이 가장 먼저 return을 수행하는 convention을 따르기 때문에 LIFO(Last-in First-out) 구조를 가지는 stack을 주로 사용합니다.

memory space에서 stack을 설명하기 위해 잠시 virtual memory 에 대해 간략히 설명하고자 합니다. virtual memory는 architecture의 memory layout이라고 볼 수 있습니다. 각각의 address는 기본적으로 아래 그림의 구조로 구성되어 있으며 각 memory 영역의 간격을 결정해주는 randomized value는 OS에 의해 결정됩니다. 이중 stack은 kernal의 바로 아래 부분에 위치해 있으며 address가 감소하는 방향으로 grow합니다. stack의 가장 작은 address 부분(stack이 grow하는 방향의 경계)을 stack top이라 하며, stack을 제어하기 위해서 stack pointer(%rsp)가 그 위치를 가리킵니다.

stack의 동작 원리를 살펴보기 위해 간단히 pushq instruction과 popq instruction의 동작에 대해 살펴보겠습니다. pushq instruction을 진행하는 과정은 먼저 %rsp를 8 감소시킨 후(word size가 8byte이므로) %rsp의 위치에 operand를 write하도록 이루어집니다. popq는 그 반대로 %rsp의 value를 read한 후 %rsp를 8 증가시키는 과정이 진행됩니다. 이때 stack에 남아있는 data는 따로 지우지 않고 나중에 해당 address로 다시 stack이 grow할 때 overwrite하는 형식으로 동작합니다.

---

Calling conventions

function call을 수행할 때는 일종의 convention이 존재합니다. 예를 들어 parameter는 어떻게 pass할 것인지(register or stack), old register value를 누가 care할 것인지(caller or callee) 등은 designer가 결정하는 영역입니다. 아래에서는 x86-64 architecture에서의 calling convention에 대해서 살펴보고자 합니다. 이후의 설명은 모두 procedure P에서 procedure Q를 call하는 상황를 가정하겠습니다.

x86-64 architecture에서 procedure가 register의 value를 저장할 공간을 필요로 할 때, stack의 memory space를 allocate 받아 저장할 수 있습니다. 해당 procedure가 allocate 받는 영역은 연속적으로 연결되어 있으며, 이를 stack frame이라 합니다. 현재 executing하는 procedure에 해당하는 stack frame은 항상 stack의 top에 위치합니다. 즉, 현재 procedure P를 수행하고 있으면 stack의 top에는 P의 stack frame이 존재하며 Q를 call하면 stack이 grow해 top이 Q의 stack frame으로 채워지게 됩니다. stack frame에는 register의 value를 저장하고 local variable을 allocate하고 argument를 set up할 수 있습니다.

Control transfer

P에서 Q로 passing control을 하는 것은 program counter(%rip)를 Q의 시작점으로 바꾸는 것 이외에도 여러 가지 처리가 필요합니다. 먼저 Q의 code가 모두 실행되고 return하는 상황에 %rip를 P의 code로 다시 돌려주어야 하기 때문에 이에 대한 record가 필요합니다. 만약 Q에서 P로 return 해야 하는 address를 A라고 한다면 function call 과정에서 stack에 A를 push 해주어야 할 것입니다. 이때 A를 return address라고 합니다. A를 push하는 것은 call instruction 수행에 즉시 following 되어야 합니다. 이후 Q에서 ret instruction 수행 시 A가 pop되어 %rip에 write 하는 동작을 진행합니다. 아래의 code를 통해 더 자세히 살펴보겠습니다.

0x400540 <multistore>:
	...
    400544:	callq 400550 <mult2>
    400541: mov %rax, (%rbx)
    ...

0x400550 <mult2>:
    400550: mov %rdi, %rax
    ...
    400557: retq 

위의 두 function에서 <multistore>는 address 0x400544의 code를 실행할 때 <mult2>를 call할 것입니다. callq instruction을 실행하기 전 stack pointer %rsp의 value가 0x120이라 하면 callq 실행과 동시에 8만큼 decrease해 0x118로 변화할 것입니다. 이후 %rsp에 return address인 0x400549를 저장하고 program counter %rip는 <mult2>의 가장 첫 부분인 0x400550이 되어 다음 cycle에 <mult2>를 실행할 것입니다. 이후 <mult2>의 instruction들을 수행해 %rsp가 다시 0x118로 돌아온 이후에 retq instruction을 실행하면 %rip에 return address를 write해주고 %rsp는 8만큼 increase해 다시 0x120이 될 것입니다. 따라서 function call 전과 return 후를 비교하면 %rsp가 원래대로 돌아오고 %rip 또한 <multistore>의 다음 instruction을 가리키고 있음을 확인할 수 있습니다.

Data transfer

procedure를 call할 때 control transfer 외에도 data를 argument로 passing하고 return value를 받아야 하기도 합니다. x86-64 architecture에서 이들 data는 대부분 register를 통해서 전달됩니다. argument를 passing할 때에는 %rdi, %rsi, %rdx, %rcx, %r8, %r9의 총 6개의 register를 우선적으로 사용하여 전달하고, return value는 %rax를 활용하여 전달해줍니다.

특수한 경우로 procedure P가 Q를 call하면서 6개를 넘는 argument를 전달해야 하기도 합니다. 이 경우에는 argument를 전달하기 위해 stack을 활용합니다. 6개의 argument는 위에서 언급한 6개의 register를 활용하고, 7번째 argument부터는 stack의 top에 push해 저장합니다. argument가 push된 이후에 program이 call instruction을 수행하기 때문에 해당 argument들은 P의 stack frame에 위치하게 됩니다.

Managing local data

대부분의 경우 procedure들은 local storage 없이 register에 모두 data를 저장할 수 있지만, 다음과 같은 경우는 local data를 memory에 저장할 필요가 있습니다.

• local data를 모두 저장할 충분한 register가 남아있지 않은 경우
• local variable에 address operator &가 적용되어 그 address를 생성할 수 있어야 하는 경우
• array 또는 structure로 저장된 data가 필요한 경우

이 경우 procedure는 stack frame에서 space를 할당받아 local variable을 저장해야 합니다. 이 중 두 번째 것을 예시로 보기 위해 아래 code를 살펴보겠습니다.

long caller() {
	long arg1 = 534;
    long arg2 = 1057;
    long sum = swap_add(&arg1, &arg2);
    long diff = arg1 - arg2;
    return sum * diff;
}

caller:
	subq	$16, %rsp			# allocate 16 byte for stack frame
    movq	$534, (%rsp)		# store 534 in arg1
    movq	$1057, 8(%rsp)		# store 1057 in arg2
    leaq	8(%rsp), %rsi		# compute &arg2
    movq	%rsp, %rdi			# compute &arg1
    call	swap_add
    movq	(%rsp), %rdx
    subq	8(%rsp), %rdx
    imulq	%rdx, %rax
    addq	$16, %rsp			# deallocate stack frame
    ret

caller라는 function에서 swap_add라는 function에 &arg1, &arg2라는 argument를 전달하기 위해 caller가 stack에서 memory를 allocate 받아 arg1, arg2를 저장하고 %rsi, %rdi에 address를 저장하는 것을 볼 수 있습니다. 이와 같이 address를 전달해야 하는 경우 local variable을 stack frame에 저장할 필요가 있습니다.

이 외의 경우는 local data를 register에 저장하는 것이 일반적입니다. 여기서 다른 function을 call할 때 이 local data를 잃지 않도록 저장하는 것이 필요한데, 여기에 두 가지 convention(caller-save, callee save)이 적용될 수 있습니다. caller-save는 callee function을 call하기 전에 미리 data를 저장해 caller가 이를 관리하는 것이고, callee-save는 callee가 caller의 local data가 저장된 register를 관리하는 것입니다.

x86-64 convention에 따라 %rbx, %rbp, %r12 ~ %r15는 callee-saved register로 분류됩니다. procedure P가 Q를 call할 때 Q는 해당 register를 보호하기 위해 이를 수정하지 않거나, register를 사용하기 위해 stack에 push하는 등의 행위를 하고 return 전에 이를 복구하는 행위를 합니다. 위의 register와 %rsp를 제외한 나머지 register들은 모두 caller-saved register로 분류됩니다. 이들은 다른 function에서 자유롭게 사용할 수 있기 때문에 caller가 다른 function을 call하기 이전에 미리 save해야 합니다.

---

Recursive procedures

앞서 define된 calling convention에 의해, stack frame을 활용한 recursive procedure 또한 자연스럽게 진행될 수 있습니다. 각각의 procedure가 private한 stack frame을 가지고 있고, stack이 local storage를 allocate / deallocate하는 policy를 구축하고 있기 때문에 여러 번 같은 function을 call하더라도 서로 다른 stack frame을 사용해 이를 온전하게 보호할 수 있습니다. 아래의 code를 예시로 해 더 자세히 살펴보겠습니다.

long rfact(long n) {
	long result;
    if (n <= 1) result = 1;
    else result = n * rfact(n - 1);
    return result;
}

rfact:
	pushq	%rbx				# save %rbx
    movq	%rdi, %rbx			# store n in callee-saved register
    movl	$1, %eax
    cmpq	$1, %rdi
    jle		.L35				# if n <= 1, goto **done:**
    leaq	-1(%rdi), %rdi		# compute n - 1
    call	rfact				# call rfact(n - 1)
    imulq	%rbx, %rax
.L35							# **done:**
    popq	%rbx				# restore %rbx
    ret

recursive하게 구현된 factorial을 계산하는 function의 예시입니다. assembly code를 살펴보면 function의 맨 첫 줄에 %rbx를 stack에 push하고 마지막에 pop을 해 caller function의 %rbx가 callee를 수행하는 동안 보호되도록 동작하고 있습니다. 이는 rfact를 여러 번 recursive하게 call하더라도 stack에 계속 저장되기 때문에 value를 잃지 않고 올바르게 수행시킬 수 있습니다.

---

reference
Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016