[크래프톤 정글 5기] week03 알고리즘 주차 스무번째 날, 프로시저, 리턴주소, 함수호출, 디스어셈블 코드 실행추적

프로시저(procedure)

- 제공되는 인수(parameter)에 따라서 특정 작업을 수행하는 서브루틴

- 프로그래밍에서의 함수(function)과 같다. 또는 메소드, 서브루틴, 핸들러 등.. 모두 프로시저라고 한다.

- 소프트웨어에서의 주요 추상화이다. 내부 동작을 숨기고, 프로시저를 통해 사용자가 쉽게 기능을 사용할 수 있게 한다.

 

프로시저가 실행될 때 처리되어야 하는 많은 과정들

프로시저 P가 프로시저 Q를 호출하고, Q가 실행된 후에 P로 리턴한다고 가정

- 제어권 전달 : 프로그램 카운터는 진입할 때 Q 코드의 시작주소로 설정된다. 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야 한다.

- 데이터 전달 : P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하고, Q는 다시 P로 하 나의 값을 리턴할 수 있어야 한다.

- 메모리 할당과 반납 : Q는 시작할 때 지역변수를 위한 공간 할당이 가능하며, 리턴할 때 이 공간을 반납할 수 있다.

 

프로시저의 구현은 레지스터, 메모리 등의 자원을 사용하는 방법에 관한 특수 인스트럭션, 그리고 일련의 관습들이 포함되어 있다. 따라서 프로시저를 호출할 때의 오버헤드를 최소화하기 위한 엄청난 노력이 시도되었으며, 결과적으로 “각 프로시저가 요구하는 메커니즘만을 최소한으로 구현”하는 전략이 사용되었다.

 

프로시저 호출 동작방식의 주요 특징

- 스택이 제공하는, 후입선출(Last in First out) 메모리 관리 방식을 활용할 수 있다.

- 스택에 프로시저의 인자, 리턴 정보, 레지스터를 저장하고 사용하며, 지역 저장공간의 목적으로 사용된다.

- x86-64 프로시저가 레지스터의 저장공간보다 넓은 공간을 필요로 할 때, 스택에 공간을 할당한다. -> 이 영역을 “스택 프레임” 이라고 한다.

 

스택

 

1. 함수 P에서 함수 Q를 실행할 때, 실행하기 전 Return address값을 먼저 스택에 삽입한다.

2. 함수 Q가 종료되고 스택에서 빠져나가면, 스택 포인터는 P의 Return Address를 가리키게 된다. Return Address는 Q가 종료된 후 P를 다시 시작할 주소가 담겨있다.

3. Return Address는 전반적으로 P에 대한 정보가 담겨 있기 때문에, 함수 P에 포함된 것으로 간주한다.

 

Q는 Top에 있으므로, 스택 포인터를 확장하여(값을 줄여) 자신의 공간을 할당한다. 이 공간 내에서 레지스터 값, 지역변수, 자신이 호출하는 프로시저를 위한 인자 등을 설정할 수 있다.

 

대부분의 프로시저, 스택 프레임들은 프로시저가 시작될 때 할당되는 고정 크기를 갖는다.

하지만 일부 프로시저는 가변 크기를 가질 수 있다.

 

인스트럭션 - call, ret

- call은 프로시저를 호출하는 인스트럭션, ret은 말 그대로 return하는 인스트럭션이다.

- 명령어가 call Q라고 가정했을 때, call은 주소 A를 스택에 푸시한 후 PC(프로그램 카운터)를 Q의 시작부분으로 설정한다.

- 푸시된 주소 A는 “리턴주소”이며, call인스트럭션의 바로 다음 주소이다. call 명령어의 바로 다음 줄이다.

- 이후 ret인스트럭션은 주소 A를 스택에서 pop해온 후 PC를 A로 세팅한다.

 

 

 

디스어셈블 코드 실행추적 해보기

디스어셈블 코드 실행추적

 

위쪽은 top, leaf, main함수에 대한 C코드를 디스어셈블 한 코드이고, 아래는 위의 코드를 실행추적한 표이다.

 

아래쪽 표를 살펴보자.

왼쪽 세 개의 열은 인스트럭션 레이블 / 주소 / 인스트럭션 유형

오른쪽 네 개의 열은 레지스터 %rdi / %ras / %rsp / 스택 탑에 담긴 값

-> %rsp는 스택 탑의 주소를 갖고 있고, *%rsp는 스택 탑에 저장된 값을 의미한다.

 

 

아래는 위와 동일한 유형의 연습문제이다.

디스어셈블 코드

 

연습문제

 

아래는 정답 사진이다.

연습문제 정답

 

각 레이블의 인스트럭션은 아직 실행되지 않았다는 가정 하에 레지스터와 주소값 등을 작성해야 한다.

M1에서 top은 e820 이었는데, callq 인스트럭션으로 First 함수로 넘어가니 top이 e818으로 8만큼 감소했고, 리턴주소가 0x400565로 갱신되었다. 0x400565는 main함수에서 callq 바로 다음 명령줄이다.

M2 레이블을 보면, F4에서 retq를 수행한 후 리턴주소인 0x400565로 돌아온 것을 볼 수 있다.

 

사실 이 연습문제는 상세히 설명한다기 보단 그냥 문제를 보면서 따라가 보면 자연스레 알 수 있다.

 

새로 배운 인스트럭션들

lea 0x2(%rdi), %rax   ->   %rdi = 95라고 했을 때, %rax에는 97이 저장된다.

lea는 “주소값을 계산”하는 인스트럭션이다.

%rdi 레지스터에 저장된 값에 0x2를 더한 값을 %rax에 할당한다.

괄호로 닫혀 있다고 해서 무조건 메모리로 가는 게 아니다. 괄호가 있다고 해도 그것이 어떤 인스트럭션이냐에 따라 갈릴 수 있다.

 

add eax, ebx -> 덧셈이다.  ebx = ebx + eax

sub eax, ebx -> 뺄셈이다.  ebx = ebx - eax

imul %rsi, %rax  ->  곱셈이다. rax = rax * rsi