[CSAPP] x86-64 - Procedures

1. 스택 (Stack)

1-1. x86-64 스택

스택(Stack)은 Stack Discipline에 의해 관리되는 메모리 영역을 말한다. Stack Discipline이란 스택을 관리하기 위한 일종의 규율과 같은 것이다. 예를 들어, x86-64에서는 %rsp 레지스터가 현재 스택의 가장 낮은 주소(Top의 주소)를 저장하기로 되어 있다. 또한 스택에 데이터가 쌓일 때는 낮은 주소 방향으로 쌓이도록 약속이 되어 있다. 따라서 데이터를 Push 할 때는 %rsp의 값을 8만큼 감소시켜야 하고, 데이터를 Pop 할 때는 %rsp의 값을 8만큼 증가시켜야 할 것이다. 

 

---

1-2. x86-64 스택 Push & Pop 명령어

x86-64에서는 스택에 데이터를 쌓기 위한 Push 명령어와 스택에서 데이터를 꺼내기 위한 Pop 명령어를 별도로 제공하고 있다. 각각의 쓰임새는 다음과 같다. 참고로 뒤에 붙은 알파벳이 q가 아닌 l이라면 %rsp의 증감 폭이 8이 아닌 4가 되어야 할 것이다.

pushq Src → 동작 : ① Src 데이터 회수, ② %rsp 8 감소, ③ %rsp 위치에 데이터 저장
popq Dest → 동작 : ① %rsp 위치의 데이터 회수, ② %rsp 8 증가, ③ Dest(반드시 레지스터)에 데이터 저장

 

2. 프로시저 메커니즘 (Procedure Mechanism)

2-1. 제어 이동 (Passing Control)

스택은 함수의 호출과 리턴 메커니즘을 뒷받침한다. 나중에 호출된 함수가 먼저 리턴하는 특성이 스택의 LIFO(Last-In First-Out) 구조와 꼭 닮았기 때문이다. x86-64에서 함수의 호출과 리턴은 각각 "callq" 명령어와 "ret" 명령어에 의해 구현된다.

callq LABEL → 함수 호출 : ① 복귀 주소를 현재 스택 프레임에 푸시(Push), ② LABEL 주소로 점프
ret → 함수 리턴 : ① 스택에 저장된 복귀 주소를 팝(Pop), ② 복귀 주소로 점프

 

다음 예시를 참고하자. 초록색으로 표시된 부분이 multstore 함수가 mult2 함수를 호출하는 명령어에 해당한다. 호출 과정에서 %rsp 레지스터와 %rip 레지스터의 값이 어떻게 바뀌어 가는지에 주목하며 호출 및 리턴의 메커니즘을 이해해 보도록 하자. (참고로 빨간색과 파란색으로 표시된 부분은 각각 Callee-save 레지스터와 Caller-save 레지스터를 백업하는 코드에 해당한다. 또한 원래대로라면 callq 명령어 바로 앞부분에 mult2 함수의 인자를 레지스터에 넣어주는 과정이 필요한데, 이미 그렇게 되어 있으므로 불필요한 코드는 생략하도록 컴파일러가 최적화한 것이다. 레지스터의 백업 및 복원 관습, 그리고 함수 인자 전달 관습에 대해서는 본 포스팅의 뒷부분 설명을 참고하자.)

 

---

2-2. 데이터 전달 (Passing Data)

함수의 1번째 ~ 6번째 인자는 %rdi, %rsi, %rdx, %rcs, %r8, %r9 레지스터에 차례로 저장이 된다. 그리고 7번째 ~ n번째 인자는 Caller의 스택 프레임에 역순서로 푸시된다. Caller는 call 명령어를 통해 또 다른 함수를 호출하기 전에 반드시 인자들을 적절한 레지스터 혹은 스택 공간에 넣어주는 작업부터 선행해야 한다. 따라서 인자가 6개보다 많으면 복귀 주소보다 인자가 먼저 스택에 쌓이게 될 것이다.

 

---

2-3. 지역 데이터의 관리 : 스택 프레임 (Stack Frame)

C, 파스칼, 자바 등의 스택 기반 언어(Stack-based Language)들은 코드가 재진입성(Reentrant)을 갖추고 있다. 즉 하나의 프로시저를 동시적으로 여러 개 인스턴스화 하는 게 가능하다는 것이다. 이를 위해서는 각 인스턴스의 상태 정보(인자, 지역 변수, 복귀 주소 등)를 저장하기 위한 공간이 필요한데, 그곳이 바로 스택이다. 구체적으로는 함수 하나가 호출될 때마다 스택 프레임(Stack Frame) 하나가 스택에 푸시되어 그곳에서 그 함수의 지역 데이터들이 관리되며, 함수가 리턴할 때 해당 스택 프레임이 스택에서 팝이 된다.

 

2-3-1. 스택 프레임의 할당 (Allocate Stack Frame)

함수를 호출할 때 실행하는 call 명령어에 의해서 복귀 주소가 Caller 스택 프레임에 푸시되고, 호출된 함수 내에서 초반부에 실행되는 "Set-up" 코드에 의해 해당 함수 내에서 필요로 하는 지역 데이터들이 할당된다.

 

2-3-2. 스택 프레임의 해제 (Deallocate Stack Frame)

호출된 함수 내에서 리턴하기 직전에 실행되는 "Finish" 코드에 의해 현재 스택 프레임에 저장되어 있는 지역 데이터들이 팝이 되고, 리턴할 때 실행하는 ret 명령어에 의해 Caller 스택 프레임에 잔존해 있던 복귀 주소도 팝을 하게 된다.

 

x86-64 리눅스 스택 프레임은 다음 그림과 같은 구조를 갖추고 있다. Caller의 스택 프레임이 저장하는 데이터를 푸시하는 순서대로 나열하자면 다음과 같다. 단 여기서 ①, ②, ③은 자기 자신의 지역 데이터를 의미하는 반면, ④와 ⑤는 새로운 함수를 호출하려고 할 때 푸시되는 정보로 Callee의 인자와 복귀 주소를 의미한다는 것에 주의하자.

 

① 기존 %rbp (Old Frame Pointer) - 필요한 경우 할당

② 백업된 레지스터들의 값 (Saved Registers) - 필요한 경우 할당 (or 레지스터에 저장)

③ 지역 변수들 (Local Variables) - 필요한 경우 할당 (or 레지스터에 저장)

④ 호출할 함수의 인자들 (Arguments) - 필요한 경우 할당 (or 레지스터에 저장)

⑤ 복귀 주소 (Return Address)

 

 

---

2-4. 레지스터의 백업 및 복원

x86-64의 레지스터는 크게 두 종류로 나뉜다. 바로 Caller-save 레지스터와 Callee-save 레지스터이다. 우선 Caller-save 레지스터는 마음껏 건드려도 괜찮은 레지스터로, 새로 호출할 함수가 그 값을 변경시켜도 할 말이 없다. 따라서 새로 호출할 함수에 의해 값이 손실되면 안 되는 경우에는, Caller가 직접 자신의 스택 프레임에 그 값을 백업하고, 나중에 해당 함수가 리턴한 직후에 다시 복원을 해야 한다. 그다음으로 Callee-save 레지스터는 함부로 건드리면 안 되는 레지스터로, 새로 함수가 호출되더라도 Caller에게 리턴했을 때 그 값이 변경되어 있으면 안 된다. 따라서 자신이 Callee-save 레지스터를 건드려야 하는 상황이라면 그전에 먼저 그 값을 자신의 스택 프레임에 백업하고, 나중에 리턴하기 직전에 다시 복원을 해야 한다.

 

다음 그림은 x86-64 레지스터들을 위 기준에 따라 분류한 것을 나타낸다.

 

 

① %rax : 반환 값이 저장되는 레지스터이다. Callee에 의해 변경될 수 있으므로 Caller-save 레지스터이다.

② %rdi ~ %r9 : 함수의 인자가 저장되는 레지스터이다. Callee에 의해 변경될 수 있으므로 Caller-save 레지스터이다.

③ %r10, %r11 : 마음껏 건드려도 괜찮은 Caller-save 레지스터이다.

④ %rbx, %r12 ~ %r14 : 함부로 건드리면 안 되는 Callee-save 레지스터이다.

⑤ %rbp : 스택 프레임의 Frame Pointer로 사용되는 레지스터로, 함부로 건드리면 안 되는 Callee-save 레지스터이다. 

⑥ %rsp : Callee-save 레지스터의 특별한 경우로, 함수 리턴 직전 "Finish" 코드에 의해 원래 값으로 복원이 된다.

 

다음 예시를 참고하자. 코드 한 줄 한 줄을 읽으면서 스택 프레임에 어떤 변화가 일어나는지도 한 번 머릿속으로 혹은 직접 펜으로 그려보기를 바란다. 그러면 함수 호출 메커니즘의 전반적인 윤곽이 잡힐 것이다.

 

 

3. 재귀 함수의 구현 (Illustration of Recursion)

앞선 설명에서 C 언어와 같은 스택 기반 언어는 재진입성(Reentrant)를 갖추고 있다고 하였다. 즉 한 프로시저에 대해 여러 개의 인스턴스가 만들어질 수 있으며, 각 인스턴스는 자신만의 지역 데이터를 관리하기 위한 스택 프레임을 가지고 있다는 것이다. 또한 스택은 함수의 호출 및 리턴 패턴(나중에 호출된 것이 먼저 리턴)을 LIFO(Last-In First-Out) 구조로서 지원하고 있다. 이러한 측면에서 봤을 때, 재귀 함수를 구현하는 것은 별도의 작업이 전혀 필요하지 않다. 단순히 또 다른 함수를 호출하는 것과 같은 메커니즘으로 처리하면 된다. 다음 예시를 살펴보자. 빨간색으로 표시된 부분이 또 다른 함수를 호출하는 문장이라고 생각해도 달라지는 것은 없다.