Chapter 7 : Machine-Level Programming 3 (Procedure)

Mechanisms in Procedures

프로시저 P가 프로시저 Q를 호출하고, Q가 실행되고 P로 다시 return됩니다.

1. Passing control

PC는 Q의 코드의 시작 주소로 설정되고, Q를 호출한 후에 P의 명령어로 설정합니다.

 

2. Passing Data

P는 하나 이상의 인자를 Q에게 제공하고, Q는 P에게 값을 다시 return합니다.

 

3. Memory management

Q는 지역변수에 대한 공간을 할당할 필요가 있습니다.

 

x86-64 Stack

x86-64에서는 %rsp 레지스터가 현재 stack의 가장 낮은 주소 (Top의 주소)를 저장합니다.

stack의 데이터가 쌓일 때는 낮은 주소 방향으로 쌓이도록 되어있습니다.

따라서 데이터를 Push할 때 %rsp의 값을 8만큼 감소시키고 데이터를 Pop할 때는 %rsp의 값을 8증가 시킵니다.

 

Push

어셈블리 명령어가 pushq Src 라면(push 뒤에 q가 아닌 l이라면 %rsp의 증감폭이 4가 되어야 합니다.)

1. Src의 데이터를 회수(fetch)

2. %rsp가 8감소

3. %rsp 위치에 데이터 저장

 

Pop

어셈블리 명령어가 popq Dest 라면(pop 뒤에 q가 아닌 l이라면 %rsp의 증감폭이 4가 되어야 합니다.)

1. %rsp의 위치한 데이터를 회수(read)

2. %rsp가 8증가

3. Dest(반드시 레지스터)에 저장

 

x86-64 Linux Memory Layout

Stack

P가 Q를 호출하고 Q가 실행하고 있는 동안 P는 정지 상태입니다.

Q가 실행되고 있을 때 , 지역 변수에 대한 새로운 공간을 할당과 다른 프로시저에 대한 호출을 설정할 필요가 

있습니다. Q가 return되면, 할당한 local 저장소를 해제합니다. 프로그램은 stack을 사용한 프로시저에 의해

요구된 저장소를 관리합니다. P가 Q를 호출하면, 제어와 데이터 정보는 stack의 마지막에 추가됩니다. 

P가 return되면 그 정보는 할당이 해제됩니다.

 

Heap

우리가 흔히 사용하는 malloc(), calloc(), new() 등 들어갑니다. (동적 데이터)

 

Data

전역변수, static 변수, 문자열 등이 들어가게 됩니다. 

 

Text / Shared Libraries

read-only, 실행가능한 명령어들을 저장

 

Passing Control

stack은 함수의 호출과 return 메카니즘을 뒷받침합니다.

x86-64에서 함수의 호출과 return은 각각 'callq' 명령어와 'ret' 명령어에 의해 구현됩니다.

어셈블리 명령어 : callq label

1. 복귀(return)주소를 현재 stack에 push

2. label 주소로 jump

어셈블리 명령어 : ret

1. stack에 저장된 복귀주소를 pop

2. 복귀주소로 jump

 

ex)

multstore 함수가 mult2 함수를 호출하는 과정입니다.

위에서 초록색 형광표시가 이에 해당합니다. %rsp 레지스터와 %rip 레지스터의 값이 어떻게 바뀌어가는지

주목하며 call 과 return의 메커니즘을 살펴보겠습니다.

 

Passing Data (데이터 전달)

함수의 1 ~ 6번째 인자는 %rdi, %rdx, %rcx, %r8, %r9 레지스터에 차례대로 저장됩니다.

7번째 ~ n번째 인자는 Caller의 stack에 역순서로 push 됩니다. Caller는 call 명령어를 통해 또 다른 함수를 

호출하기 전에 반드시 인자들을 적절한 레지스터 혹은 stack 공간에 넣어주는 작업부터 선행되어야 합니다. 

따라서 인자가 6개보다 많으면 복귀주소 보다 인자가 먼저 stack에 쌓이게 됩니다.

 

Managing local data

C, Pascal, JAVA 등의 Stack-based Language들은 코드가 reentrant(재진입성)을 갖추고 있습니다.

즉, 하나의 프로시저를 동시적으로 여러 개 instance화 하는 게 가능하다는 것입니다.

이를 위해서는 각 instance의 정보(인자, 지역변수, 복귀주소 등)을 저장하기 위한 공간이 필요합니다. 

그곳이 바로 Stack 입니다. 

구체적으로 함수 하나가 호출될 때 마다 stack frame 하나가 push되어 그곳에서 해당 함수의 지역 데이터들이

관리되면, 함수가 return할때 stack frame이 stack에서 pop됩니다.

Stack Frame

Allocate Stack Frame

함수를 호출할 때 실행하는 call 명령어에 의해 복귀주소가 Caller stack frame에 push되고, 호출된 함수 내에서

초반부에 실행되는 "Set-up" 코드에 의해 해당 함수 내에서 필요로 하는 지역 데이터들이 할당됩니다.

Deallocate Stack Frame

호출된 함수 내에서 return하기 직전에 실행되는 "Finish" 코드에 의해 현재 stack frame에 저장되어 있는 

지역 데이터들이 pop되고, return할 때 실행하는 ret명령어에 의해 Caller stack frame에 보존해 있던 복귀주소도

pop을 하게 됩니다.

 

ex)

 

x86-64 / Linux Stack Frame

Caller의 stack frame이 저장하는 데이터를 push하는 순서대로 나열하면 다음과 같습니다.

1. 기존 %rbp (Old Frame Pointer)

2. 백업된 레지스터들의 값 (Saved Register)

3. 지역 변수들 (Local Variables)

4. 호출할 함수의 인자들 (Arguments)

5. 복귀 주소(Retrun Address)

1, 2, 3번은 자기 자신의 지역 데이터를 의미하고 4, 5번은 새로운 함수를 호출하려고 할 때 push되는 정보로

Callee의 인자와 복귀주소를 의미합니다.

 

ex) call_incr() 에서 incr 함수 부르기

incr 함수

 

Register Saving Conventions

위의 함수를 보면 yoo가 caller이고 who가 callee입니다.

레지스터 %rdx가 who함수에 의해 덮여씌어질 수 있습니다. 이렇게 되면 문제를 일으킵니다.

Caller saved

마음껏 건드려도 괜찮은 레지스터로, 새로 호출할 함수가 그 값을 변경시켜도 상관없습니다.

따라서 새로 호출할 함수에 의해 값이 손실되면 안 되는 경우에는, Caller가 직접 stack frame에 그 값을 백업하고,

나중에 해당 함수가 return 직후에 다시 복원을 해야합니다.

Callee Saved

함수로 건드리면 안되는 레지스터입니다. 새로 함수가 호출되더라도 Caller에게 리턴했을 때 

그 값이 변경되어 있으면 안됩니다. 따라서 자신이 Callee-save 레지스터를 건드려야 하는 상황이라면 

먼저 그 값을 자신의 stack frame에 백업하고, 나중에 return 하기 직전에 다시 복원을 해야 합니다.

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

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

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

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

%rbp : stack frame의 Frame Pointer로 사용되는 레지스터로, 함부로 건드리면 안되는 Callee-save 레지스터

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

 

ex)

pushq %rbx : Callee-save 레지스터 백업

subq $16, %rsp : 지역변수 공간 할당

movq %rdi, %rbx : Caller-save 레지스터 백업

movq $15213, 8(%rsp) : 지역 변수 초기화

movl $3000, %esi : 2번째 인자 전달

leaq 8(%rsp), %rdi : 1번째 인자 전달

call incr : incr 함수 호출

addq %rbx, %rax : return값 저장

addq $16, %rsp : 지역 변수 공간 해제

popq %rbx : Callee-save 레지스터 복원

ret : 함수 return

 

Illustration of Recursion

stack-based 언어는 reentrant(재진입성)을 갖추고 있습니다.

즉, 한 프로시저에 대해 여러개의 instance가 만들어 질 수 있으며, 각 instance는 자신만의 지역 데이터를

관리하기 위한 stack frame을 가지고 있는 것입니다.

또한 stack은 함수의 호출 및 return 패턴을 LIFO(나중에 호출된 것이 먼저 return)구조로서 지원합니다.

즉, 재귀함수는 단순히 또 다른 함수를 호출하는 것과 같은 메커니즘으로 처리하면 됩니다.

 

ex) 2진수에서 1의 개수를 세는 함수입니다.

pushq %rbx : Callee-save 레지스터 백업

movq %rdi, %rbx : Caller-save 레지스터 백업

call pcount_r : 함수호출 (재귀함수가 아니라 그냥 다른 함수를 호출한다고 가정해도 문제없습니다.)

popq %rbx : Callee-save 레지스터 복원