[CS] Call Stack Procedure - Computer System 3rd Edition by Bryant

컴퓨터의 모든 코드는 어떠한 '흐름'으로 동작한다.

순차적이든, 병렬적이든 코드들은 정해진 Procedure에 의해 동작을 하게 되는데,

이번에는 Procedure Call이 어떻게 동작하는지 알아보자. 

 

C도 그렇고 대부분의 프로그래밍 언어는 함수로 동작을 한다.

C/C++같은 경우는 main에서 함수가 동작을 하는데 우리는 프로그래밍을 하면서 수많은 함수들을 짜게 된다.

이때 Procedure에서 함수를 부르는 친구를 caller라고 하고, 호출되는 함수를 callee라고 한다.

Process를 실행시키기 위해 Program은 메모리에 올라가게 되고 Running State에 들어가게 되면 CPU는 적절하게 명령을 수행하며 다양한 Procedure Call이 불린다. Calling을 할때는 ISA마다 다른 규약을 지니고 있어 다를 수도 있겠지만, 본 포스팅은 책에 맞게 x86-64/Linux ISA에 맞게 설명을 진행하겠다. 

Stack

Procedure Call을 위해서는 caller, callee의 주소나 arguments, 복귀 주소, register 정보 등 다양한 정보를 어딘가에는 저장을 해야한다. 이 정보들은 메모리에 Stack이라는 공간에 저장된다. 

자료구조 시간에 배우는 그 Stack이 맞다.

LIFO의 자료구조를 지닌 공간으로서 복귀주소, args, local variable 등 다양한 정보를 여기에 저장을 한다. 

call과 ret instruction을 통해서 Stack을 관리한다. 

아래의 그림은 Stack에서 복귀주소를 저장하는 flow를 보여준다. 

메인 메모리가 4000번지, Proc1이 4500번지, Proc2가 4800번지에서 시작한다고 가정했을 때 Call Proc1이 실행될 때 4101번지가 Stack에 저장된다. 이때 왜 4100이 아니라 4101이냐는 의문이 생길 수 있지만 돌아와서 수행해야하는 주소를 적어놓은 것이다. Proc1을 수행하고 Proc2가 호출이 되면 4601번지를 Stack에 push하고, Proc2의 수행이 끝나면 pop해서 복귀를 하게 된다. 이런식으로 복귀할 주소를 push, pop을 반복하는 작업을 한다. 

RSP & RBP Register

x86-64 ISA에는 이러한 stack의 주소를 관리해주는 두 개의 레지스터가 존재하는데, 이는 %rbp, %rsp 레지스터이다.

%rbp레지스터는 base pointer, 혹은 frame pointer라고도 부르고, %rsp는 stack의 top을 가리킨다.

Stack은 Stack Frame이라는 것을 지니고 있다. 예를들어서 아래의 f1을 수행할 때 Stack Frame은 f1의 Stack Frame을 지니고 있고, f2는 f2만의 Stack Frame을 지니고 있다. 이를 activation frame을 가지고 있는데, 결국 Stack Frame은 각 Procedure의 Information지니고 있다. 그래서 rsp, rbp 레지스터는 각 Stack Frame의 끝주소, 시작주소를 가리키고 있다는 것이 과언이 아니다. 

f1() {
    ....
    f2();
    ....
}

f2() {
    ...
    f3();
    ...
}

대충 이런 코드가 있다고 하자. 이 코드들의 flow를 따라가면 f1 -> f2 -> f3 순으로 Procedure가 Call되고 있다.

그래서 rbp, rsp 레지스터도 Procedure들이 호출이 될때마다 각각의 Stack Frame을 유지시켜주기 위해 움직이게 된다. 

그 변화는 아래의 그림과 같다.

 

Controlling Stack

Stack은 특이하게도 크기가 점점 커질수로 메모리 주소 번지가 감소한다. 일반적으로는 Memory 주소가 점점 커져야 하는 것이 맞지만, Stack은 특이하게도 주소가 점점 감소하므로 이를 유의하자.

Stack Frame에는 return address, old frame pointer, local variables, saved register context, arguments등이 담긴다.

복귀주소는 당연하고, old frame pointer는 rsp를 이동시키기 위해서 필요하다. 컴퓨터공학도라면 local variable은 stack에 담긴다는 것을 알고 있을 것이다. saved register context는 register의 정보들을 담고 있는데 이는 운영체제에서 자세히 배우게 될 것이다. arguments들은 stack을 통해서 전달이 된다. 

 

pushq instruction은 스택의 크기를 늘리는 역할을 한다. push quad word의 의미인데, -8만큼 크기를 늘린다.

앞서서 Stack은 메모리 번지가 감소하는 것으로 크기를 늘린다고 했는데 -8을 해주는 의미가 이때문이다. 

 

popq instruction은 pop quad word의 의미로, 먼저 rsp의 value를 dst에 저장을 하고, rsp의 크기를 +8만큼 줄인다. 

dst는 보통 rbp 레지스터가 많이 온다. 그리고 이번에는 Stack의 크기를 줄이는 것이므로 +8을 해줘야한다. 

아래의 그림을 본다면 이해에 도움이 될 것이다. 

앞서서 call과 ret으로 Stack을 관리한다고 잠깐 언급한 적이 있었다.

그 전에 rip 레지스터라는 것이 있는데, 이는 return address, 즉 fetch 할 명령어의 주소를 저장하는 register이다

call addr 명령어를 수행하게 되면 두 가지 operation을 개념적으로 수행한다. 

먼저 stack pointer인 rsp를 8만큼 줄여 스택에 공간을 만든다. 그리고 rip에 담겨있는 return address를 stack의 최상단에 push하게 된다. 여기까지가 하나의 작업인데 이는 개념적으로 pushq operation과 같다. 그 다음 작엄은 %rip 레지스터의 주소를 addr로 바꾼다. 개념적으로 jmp addr과 비슷하다고 생각한다.

문제는 call instruction은 개념적으로 pushq, jmp와 같다는 것이지 이렇게 사용하면 에러가 발생하게 된다.

ret 은 당연하게도 popq %rip와 같은 작업을 수행한다. 

 

int main() {
    int x = 4;
    int y = 8;
    int z = x + y;
    return 0;
}

위와같은 간단한 코드가 있다고 하자. 이를 어셈블리 코드로 한번 따라가보면서 어떻게 작동하는지 알아보자.

main:
    push %rbp
    mov %rsp, %rbp
    sub $16, %rsp
    
    movl $0x4, -12(%rbp)
    movl $0x8, -8(%rbp)
    mov -12(%rbp), %edx
    mov -8(%rbp), %eax
    add %edx, %eax
    mov %eax, -4(%rbp)
    mov $0x0, %eax
    
    leavq
    retq

 먼저 rbp라는 base pointer를 저장시켜야 한다. de-allocation, 즉 하나의 Stack Frame(Procedure)가 끝나면 돌아올 때 돌아오는 Stack의 Stack Frame을 유지시켜야 하기 때문이다. 그렇다면 다음에는 rbp의 주소를 rsp에 맞춰서 새로운 Stack Frame에 들어가게 된다. 그리고 16byte 공간의 Stack Memory 확보를 위해 rsp의 주소를 -16을 해주게 된다. 위에 세 줄의 assembly는 새로운 Stack Frame을 위한 Set-Up Code라고 이해하면 될 것이다.

 

 이제는 body를 수행해야 할 차례이다. 각각의 x, y는 int형이기 때문에 4byte씩 rbp의 상대주소에 저장한다. 

그 다음은 계속 계산을 하는 영역이 나오고 마지막으로 eax 레지스터, 즉 return register에 0을 저장한다. 

 

 마지막은 작업을 마친 Stack의 Frame을 de-allocate시키는 부분이다. 

 

이 코드의 특이한 점은 Stack에서는 실제로 12byte만 사용되고 있는데, Stack을 initialize 해줄 때는 16byte만큼 사용하기 위해 주소를 낮추고 있다. 이는 각 ISA마다 다르겠지만 혹시 모를 상황을 대비할 reserve 영역이라고 생각하면 되겠다. 

 

Procedure Call이 발생을 할때 대부분의 경우에는 argument가 전달되어 함수가 동작한다. 이때 6개 정도의 argument들은 효율성을 위해 바로 레지스터를 통해 전달이 되는데, 이는 %rdi, %rsi, $rdx, $rcx, %r8, %r9 레지스터이다. 만약 이보다 더 많은 수의 argument를 전달하고 싶다면 stack을 통해 memory로 전달이 된다. 

위에서 살펴본 어셈블리는 최적화 옵션이 적용되지 않은 상태이다.

일반적으로 Linux 환경에서 c를 컴파일 할 때 gcc -o filename.c 이렇게 .out 파일을 만들지만, -oo, -og 옵션을 통해서 최적화를 낮추어 줄 수 있다. 최적화 레벨을 낮출수로 assembly 코드는 user-friendly하게 코드가 컴파일된다. 반면 -o3 옵션같이 최적화 옵션이 높을수록 레지스터에서 바로 계산을 해버릴 수도 있다. 이는 local variable도 stack에 저장되면서 진행되는게 아니라 register 내에서 계산이 완료되기 때문에 현재 우리가 지금까지 본 코드들은 전부 최적화 옵션이 낮은 상태에 있다. 또한 주의할 점은 각 CPU나 환경이 다르기 때문에 assembly 코드는 컴퓨터 마다 다른 결과가 나올 수 있음에 유의하자. 

 

Reference

Randal E. Bryant, & David R. O’Hallaron. (2016). Computer Systems A Programmer’s Perspective Third edition. Carnegie Mellon University: Pearson.

Stalling, William. Operating Systems: Internals and Design Principle. Pearson, 2018.